tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU2019: Cornfields

なんか頭のいい解法があるらしいのですが(多分範囲のサイズが決まってることを利用して累積和っぽいことをする)、見た瞬間に二次元のSegmentTreeだ!とか言って二次元Segtree書いていました。

二次元Segtreeのソースとしてあげてみます。
やっていることは、普通のSegtreeのクエリ関数を二次元にしただけですが、一つ目の次元の範囲を先に決めてから二つ目の次元の範囲を決めてやります。初期化とかも二重ループになります。あとは普通のSegtreeと同じです。慣れれば多分簡単に書けると思います。まだ慣れていませんorz...

#include<stdio.h>
#include<algorithm>
using namespace std;
int segtree1[512][512];//max
int segtree2[512][512];//min
int query(int a,int b,int c,int d,int e,int f,int g,int h,int i,int j,int type){
	if(f<a||e>b||h<c||g>d){
		return type==1?0:999;
	}
	if(a<=e&&f<=b){
		if(c<=g&&h<=d)return type==1?segtree1[i][j]:segtree2[i][j];
		else return type==1?max(query(a,b,c,d,e,f,g,(g+h)/2,i,j*2,1),query(a,b,c,d,e,f,(g+h)/2+1,h,i,j*2+1,1)):
		min(query(a,b,c,d,e,f,g,(g+h)/2,i,j*2,2),query(a,b,c,d,e,f,(g+h)/2+1,h,i,j*2+1,2));
	}else{
		return type==1?max(query(a,b,c,d,e,(e+f)/2,g,h,i*2,j,1),query(a,b,c,d,(e+f)/2+1,f,g,h,i*2+1,j,1)):
		min(query(a,b,c,d,e,(e+f)/2,g,h,i*2,j,2),query(a,b,c,d,(e+f)/2+1,f,g,h,i*2+1,j,2));
	}
}
void set(int a,int b,int c){
	a+=256;
	b+=256;
	while(a){
		int d=b;
		while(d){
			segtree1[a][d]=max(segtree1[a][d],c);
			segtree2[a][d]=min(segtree2[a][d],c);
			d/=2;
		}
		a/=2;
	}
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<512;i++)
		for(int j=0;j<512;j++)
			segtree2[i][j]=999;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			int d;
			scanf("%d",&d);
			set(i,j,d);
		}
	}
	for(int i=0;i<c;i++){
		int e,f;
		scanf("%d%d",&e,&f);
		printf("%d\n",query(e-1,e+b-2,f-1,f+b-2,0,255,0,255,1,1,1)-query(e-1,e+b-2,f-1,f+b-2,0,255,0,255,1,1,2));
	}
}