PKU2777 Count Color

数年前からそろそろ解かねばなあということで思っていたのでついに解きました。
遅延更新のsegtreeってこう書くんですね。なれとかないと。
ちなみにクエリで与えられる範囲の値が左右逆になることもあるらしいです。普通気がつかないと思う。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[2];
int segtree[524288];
int flag[524288];
void paint(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		flag[e]=1;
		segtree[e]=(1<<f);
		return;
	}
	if(flag[e]){
		flag[e]=0;
		segtree[e*2]=segtree[e*2+1]=segtree[e];
		flag[e*2]=flag[e*2+1]=1;
	}
	paint(a,(a+b)/2,c,d,e*2,f);
	paint((a+b)/2+1,b,c,d,e*2+1,f);
	segtree[e]=segtree[e*2]|segtree[e*2+1];
}
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d){
		//printf("%d %d %d %d %d: %d\n",a,b,c,d,e,segtree[e]);
		return segtree[e];
	}
	if(flag[e]){
		flag[e]=0;
		segtree[e*2]=segtree[e*2+1]=segtree[e];
		flag[e*2]=flag[e*2+1]=1;
	}
	int ret=query(a,(a+b)/2,c,d,e*2)|query((a+b)/2+1,b,c,d,e*2+1);
	//printf("%d %d %d %d %d: %d\n",a,b,c,d,e,ret);
	return ret;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	paint(0,131071,0,a-1,1,0);
	for(int i=0;i<c;i++){
		scanf("%s",str);
		if(str[0]=='C'){
			int p,q,r;
			scanf("%d%d%d",&p,&q,&r);
			if(p>q){int s=p;p=q;q=s;}
			paint(0,131071,p-1,q-1,1,r-1);
		}else{
			int p,q;
			scanf("%d%d",&p,&q);
			if(p>q){int s=p;p=q;q=s;}
			int val=query(0,131071,p-1,q-1,1);
			int ret=0;
			for(int j=0;j<b;j++)if(val&(1<<j))ret++;
			printf("%d\n",ret);
		}
	}
}