ZOJ 2859 二维线段树 - c++编程基础

TOP

ZOJ 2859 二维线段树

2015-07-20 17:57:22 来源: 作者: 【大中小】浏览:2次

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

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 3273（原来以为是dp呢，居然..	下一篇：POJ 2486 树形DP

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: