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) )でセグメントツリーを合体させた(いらないところ(最大、最小とならない)を削った)もの。