题目链接:

题意：给出一个n*n的矩阵。每次询问子矩阵的最小值。

思路：节点保存的是一个区间。孩子是将该区间分成四个小矩阵。

const int INF=1000000000;const int N=305;struct node{    int Min,x[2],y[2],son[4];    node(){}    node(int x0,int y0,int x1,int y1)    {        x[0]=x0;        x[1]=x1;        y[0]=y0;        y[1]=y1;        Min=INF;        clr(son,0);    }};node a[N*N*5];int e,n,b[N][N];int C;void up(int t){    int i;    FOR0(i,4)    {        a[t].Min=min(a[t].Min,a[a[t].son[i]].Min);    }}void build(int t,int x0,int y0,int x1,int y1){    a[t]=node(x0,y0,x1,y1);    if(x0==x1&&y0==y1)    {        a[t].Min=b[x0][y0];        return;    }    int i;    FOR0(i,4) a[t].son[i]=++e;    int midX=(x0+x1)>>1;    int midY=(y0+y1)>>1;    int midX1=midX
     
      a[t].x[1]||x1
      
       a[t].y[1]||y1
       
        =a[t].x[1]&&y0<=a[t].y[0]&&y1>=a[t].y[1])    {        return a[t].Min;    }    int ans=INF,i,temp;    FOR0(i,4)    {        temp=query(a[t].son[i],x0,y0,x1,y1);        ans=min(ans,temp);    }    return ans;}int main(){    RD(C);    while(C--)    {        RD(n);        int i,j;        FOR1(i,n) FOR1(j,n) RD(b[i][j]);        build(0,1,1,n,n);        int x0,y0,x1,y1,m;        RD(m);        while(m--)        {            RD(x0,y0);            RD(x1,y1);            PR(query(0,x0,y0,x1,y1));        }    }    return 0;}