ZOJ 2859 二维线段树

思路：自己写的第二发二维线段树1A。哈哈，看来对二维的push操作比較了解了；可是还没遇到在两个线段树中同一时候进行push操作的，事实上这题我是想在x维和y维同一时候进行push操作的。可是想了好久不会。然后看到这题又给出10秒，然后想想在x维线段直接单点查询肯定也过了，然后在第二维就仅仅有pushup操作。在第一维线段树没有pushup操作。要是在第一维也有pushup操作的话。那就不用单点查询那么慢了。

只是也A了，想找题即在二维同一时候进行pushup和pushdown操作的。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<queue>

#include<set>

#include<cmath>

#include<bitset>

#define mem(a,b) memset(a,b,sizeof(a))

#define lson i<<1,l,mid

#define rson i<<1|1,mid+1,r

#define llson j<<1,l,mid

#define rrson j<<1|1,mid+1,r

#define INF 0x7fffffff

#define maxn 1010

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

int Map[maxn][maxn],Min[maxn][maxn];

int n,q,t,ans;

void pushup(int i,int j)

{

    Min[i][j]=min(Min[i][j<<1],Min[i][j<<1|1]);

}

void build_y(int i,int u,int j,int l,int r)

{

    if(l==r)

    {

        Min[i][j]=Map[u][l];

        return ;

    }

    int mid=(l+r)>>1;

    build_y(i,u,llson);build_y(i,u,rrson);

    pushup(i,j);

}

void build_x(int i,int l,int r)

{

    if(l==r)

    {

        build_y(i,l,1,1,n);

        return ;

    }

    int mid=(l+r)>>1;

    build_x(lson);build_x(rson);

}

int query_y(int i,int j,int l,int r,int y1,int y2)

{

    if(l==y1&&y2==r) return Min[i][j];

    int mid=(l+r)>>1;

    if(y2<=mid) return query_y(i,llson,y1,y2);

    else if(y1>mid) return query_y(i,rrson,y1,y2);

    else return min(query_y(i,llson,y1,mid),query_y(i,rrson,mid+1,y2));

}

void query_x(int i,int l,int r,int x1,int x2,int y1,int y2)

{

    if(l==r)

    {

        ans=min(ans,query_y(i,1,1,n,y1,y2));

        return ;

    }

    int mid=(l+r)>>1;

    if(x1<=mid) query_x(lson,x1,x2,y1,y2);

    if(x2>mid) query_x(rson,x1,x2,y1,y2);

}

int main()

{

    freopen("test.txt","r",stdin);

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                scanf("%d",&Map[i][j]);

        build_x(1,1,n);

        scanf("%d",&q);

        while(q--)

        {

            int x1,y1,x2,y2;

            ans=INF;

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            query_x(1,1,n,x1,x2,y1,y2);

            printf("%d\n",ans);

        }

    }

    return 0;

}