OUPC2012 問題J Range Minimum Query (AOJ2359)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2359）

制約条件

Q≦5*10^4
tiは0か1
a[i]≦b[i]≦10^9
y[i]≦10^9

方針

解説スライド（http://www.slideshare.net/oupc）がわかりやすい（？）
そんなにわかりやすくもなかった。

まずは出てくる座標が大きいので座標圧縮する。
区間は半開区間として扱うと楽なのでa[i],b[i]+1を座標圧縮する。

まずは初期値の候補を探す。
初期値の候補は、最小値を与えるクエリがきたら、その区間での初期値の下限が決まる。
代入がきたら、その区間での今の下限を初期値としていい。

これで初期値を作って、ダメだったら不可能。

区間に対するz[i]=max(z[i],y)の操作と、区間に一様に代入する操作は、
愚直にやるとTLEなので、区間木やバケット法を使う。

バケット法でやった。

ソースコード

const int sz=256, MX=60000;
int q,t[MX],a[MX],b[MX],y[MX];
int vs[MX*2],init[MX*2],m;
int z[MX*2],mx[1000];
bool eq[1000],initialized[1000];

//区間に対してz[i]=max(z[i],x)の操作をする
inline void takemax(int i,int j,int x){
	bool flag=eq[i/sz];
	while(i<j&&i%sz){
		if(eq[i/sz])rep(k,sz)z[i/sz*sz+k]=mx[i/sz];
		eq[i/sz]=0; z[i]=max(flag?mx[i/sz]:z[i],x);
		i++;
	}
	flag=eq[(j-1)/sz];
	while(i<j&&j%sz){
		if(eq[--j/sz])rep(k,sz)z[j/sz*sz+k]=mx[j/sz];
		eq[j/sz]=0; z[j]=max(flag?mx[j/sz]:z[j],x);
	}
	i/=sz; j/=sz;
	if(i&&!eq[i-1]){
		mx[i-1]=inf;
		rep(k,sz)mx[i-1]=min(mx[i-1],z[(i-1)*sz+k]);
	}
	if(!eq[j]){
		mx[j]=inf;
		rep(k,sz)mx[j]=min(mx[j],z[j*sz+k]);
	}
	while(i<j){
		if(eq[i]||mx[i]>=x)mx[i]=max(mx[i],x);
		else{
			mx[i]=inf;
			rep(k,sz)z[i*sz+k]=max(z[i*sz+k],x), mx[i]=min(mx[i],z[i*sz+k]);
		}
		i++;
	}
}
//区間に対して一様にz[i]=xを代入する
//初回では、代入の際に初期値が決まるので、初回の場合だけ初期値を取り出す
inline void set(int i,int j,int x,bool ini=0){
	bool flag=eq[i/sz];
	while(i<j&&i%sz){
		if(ini&&!initialized[i/sz]&&init[i]==-inf)init[i]=flag?mx[i/sz]:z[i];
		if(eq[i/sz])rep(k,sz)z[i/sz*sz+k]=mx[i/sz];
		eq[i/sz]=0; z[i++]=x;
	}
	flag=eq[(j-1)/sz];
	while(i<j&&j%sz){
		j--;
		if(ini&&!initialized[j/sz]&&init[j]==-inf)init[j]=flag?mx[j/sz]:z[j];
		if(eq[j/sz])rep(k,sz)z[j/sz*sz+k]=mx[j/sz];
		eq[j/sz]=0; z[j]=x;
	}
	i/=sz; j/=sz;
	if(i&&!eq[i-1]){
		mx[i-1]=inf;
		rep(k,sz)mx[i-1]=min(mx[i-1],z[(i-1)*sz+k]);
	}
	if(!eq[j]){
		mx[j]=inf;
		rep(k,sz)mx[j]=min(mx[j],z[j*sz+k]);
	}
	while(i<j){
		if(ini&&!initialized[i]){
			rep(k,sz)if(init[i*sz+k]==-inf)init[i*sz+k]=eq[i]?mx[i]:z[i*sz+k];
			initialized[i]=1;
		}
		eq[i]=1; mx[i++]=x;
	}
}
//区間に対してmin(z[i])を求める
inline int get(int i,int j){
	int res=inf;
	while(i<j&&i%sz)res=min(res,eq[i/sz]?mx[i/sz]:z[i]), i++;
	while(i<j&&j%sz)res=min(res,eq[--j/sz]?mx[j/sz]:z[j]);
	i/=sz; j/=sz;
	while(i<j)res=min(res,mx[i++]);
	return res;
}

//初回は、チェックはせず、初期値の構成をする
//二回目は初期値の構成はせず、値のチェックをする
bool func(bool ck){
	rep(i,q){
		if(t[i]==0){
			if(!ck)takemax(a[i],b[i],y[i]);
 			else if(get(a[i],b[i])!=y[i]) return 0;
		}
		else set(a[i],b[i],y[i],!ck);
	}
	if(!ck)rep(i,m)if(init[i]==-inf)init[i]=eq[i/sz]?mx[i/sz]:z[i];
	return 1;
}

int main(){
	scanf("%d",&q);
	rep(i,q){
		scanf("%d%d%d%d",t+i,a+i,b+i,y+i);
		vs[2*i]=a[i]; vs[2*i+1]=++b[i];
	}
	sort(vs,vs+2*q);
	m=unique(vs,vs+2*q)-vs;
	rep(i,q){
		a[i]=lower_bound(vs,vs+m,a[i])-vs;
		b[i]=lower_bound(vs,vs+m,b[i])-vs;
	}
	
	rep(i,m)z[i]=init[i]=-inf;
	rep(i,(m+sz-1)/sz)mx[i]=-inf, eq[i]=1;
	func(0);
	rep(i,m)z[i]=init[i];
	rep(i,(m+sz-1)/sz){
		eq[i]=1; mx[i]=inf;
		rep(j,sz)if(i*sz+j<m){
			mx[i]=min(mx[i],z[i*sz+j]);
			if(z[i*sz]!=z[i*sz+j])eq[i]=0;
		}
	}
	puts(func(1)?"YES":"NO");
	return 0;
}