POJ2777

タイトルの説明:
色板の長さはLで、Lは正の整数なので、Lブロックの長さ1センチの小さな四角形に均一に分けることができます.左から1,2,...L.今色板の上でただ1つの色だけあって、先生は宝に色板の上で2つの事しかできないことを教えます:1.「C A B C」とは、AからB番の格子に色Cを塗ることを意味する.2.「P A B」は先生の質問です.AからB番の四角い格子にはいくつかの色があります.学校の絵の具箱には全部でT種類の絵の具が入っています.簡単にするために、私たちは彼らを1、2とマークしました.T.最初は色板の元の色が1番色になります.このような複雑な問題に直面して、宝さんはあなたに助けを求めて、あなたは彼を助けることができますか?
方法:
これは線分の木+状圧のいい問題です.明らかにTは特に小さく、つまり色の種類が少ない.では、色を状態圧縮することができます.
i番目の色は2^(i-1)という数を表し、1つの区間に対応する数が2進数に変換されてi番目のビットが1になると、i番目の色が塗られていることを表します.そして線分の木の上に置いてやればいいのです
ここではビット操作|で色の種類をマージできます
コードは次のとおりです.

#include
#include
#include
#include
#include
#include
using namespace std;
int d[40005],b[400005],c[400005],e[400005];
int n,m,x,y,T,z;
char ch;
void build(int k,int x,int y)
{
	b[k]=x; c[k]=y;
	if (x==y){
		d[k]=1;
		e[k]=1;
		return;
	}
	int mid=(x+y)/2;
	build(k*2,x,mid);
	build(k*2+1,mid+1,y);
	d[k]=1; e[k]=0;
}
void maintain(int k)
{
	d[k*2]=d[k];//        
	d[k*2+1]=d[k];
	e[k*2]=e[k];
	e[k*2+1]=e[k];
	e[k]=0;
}
void add(int k,int x,int y,int z)
{
	if (x>c[k]||y=c[k]){
		d[k]=(1<mid) add(k*2+1,x,y,z);
	else if (x<=mid&&y>mid){
		add(k*2,x,mid,z);
		add(k*2+1,mid+1,y,z);
	}
	d[k]=d[k*2]|d[k*2+1];
}
int sum(int k,int x,int y)
{
	if (x<=b[k]&&y>=c[k]) return d[k];
	if (e[k]) maintain(k);
	int mid=(b[k]+c[k])/2;
	if (y<=mid) return sum(k*2,x,y);
	if (x>mid) return sum(k*2+1,x,y);
	if (x<=mid&&y>mid) return sum(k*2,x,mid)|sum(k*2+1,mid+1,y); 
}
int main()
{
	scanf("%d%d%d",&n,&m,&T);
	build(1,1,n);
	while (T--){
		cin>>ch;
		if (ch=='C'){
			scanf("%d%d%d",&x,&y,&z);
			if (x>y) swap(x,y);
			add(1,x,y,z);
		}
		else {
			scanf("%d%d",&x,&y);
			if (x>y) swap(x,y);
			int sum1=sum(1,x,y);
			int ans=0;
			while (sum1){
				if (sum1%2) ans++;
				sum1=sum1/2;
			}
			printf("%d
",ans);
		}
	}
	return 0;
}