UVa 11297 Census
問題 : UVa Online Judge
二次元のセグメントツリーで値の更新、クエリに対して矩形内の最大値、最小値を求める。
#include<iostream> #include<stdio.h> using namespace std; const int MAX_N=500; const int INF=200000000; struct info{ info(){} info(int mi_,int ma_):mi(mi_),ma(ma_){} int mi; int ma; }; info seg[4*MAX_N][4*MAX_N]; int n; void init(int n_){ n=1; while(n<n_)n*=2; for(int i=0;i<2*n-1;i++){ for(int j=0;j<2*n-1;j++){ seg[i][j]=info(INF,-1); } } } void update(int a,int b,int x){ b+=n-1; a+=n-1; seg[a][b]=info(x,x); int r=b; while(a>0){ r=b; while(r>0){ r=(r-1)/2; seg[a][r]=info(min(seg[a][2*r+1].mi,seg[a][2*r+2].mi),max(seg[a][2*r+1].ma,seg[a][2*r+2].ma)); } a=(a-1)/2; seg[a][b]=info(min(seg[2*a+1][b].mi,seg[2*a+2][b].mi),max(seg[2*a+1][b].ma,seg[2*a+2][b].ma)); } } info query(int a,int x1,int x2,int k,int l,int r){ if(x1>=r || x2<=l)return info(INF,-1); if(x1<=l && x2>=r){ return seg[a][k]; } else{ info ql=query(a,x1,x2,2*k+1,l,(l+r)/2); info qr=query(a,x1,x2,2*k+2,(r+l)/2,r); return info(min(ql.mi,qr.mi),max(ql.ma,qr.ma)); } } info main_query(int x1,int y1,int x2,int y2,int k,int l,int r){ if(y1>=r || y2<=l)return info(INF,-1); if(y1<=l && y2>=r){ return query(k,x1,x2,0,0,n); } else{ info ql=main_query(x1,y1,x2,y2,2*k+1,l,(l+r)/2); info qr=main_query(x1,y1,x2,y2,2*k+2,(r+l)/2,r); return info(min(ql.mi,qr.mi),max(ql.ma,qr.ma)); } } int main(){ int N; cin>>N; init(N); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ int t; scanf("%d",&t); update(i,j,t); } } int Q; cin>>Q; for(int i=0;i<Q;i++){ char q; scanf(" %c",&q); if(q=='q'){ int x1,y1,x2,y2; scanf("%d%d%d%d",&y1,&x1,&y2,&x2); info ans=main_query(x1-1,y1-1,x2,y2,0,0,n); printf("%d %d\n",ans.ma,ans.mi); } else{ int x,y,v; scanf("%d%d%d",&y,&x,&v); update(y-1,x-1,v); } } }
バグを生やし続けて辛かった。
(今回の)二次元のセグメントツリーについて:
一次元のセグメントツリーseg[a]が値でなくセグメントツリーを持っている。
seg[a]は結果的に(子を持てば)seg[a][k].ma=max(seg[2*a+1][k].ma,seg[2*a+2][k].ma)
seg[a][k].miも同様、となっている。つまり、seg[a]はaに対応する区間(ex.a=0 -> [0,n) )でセグメントツリーを合体させた(いらないところ(最大、最小とならない)を削った)もの。