poj(2777)——Count Color(lazy思想、セグメント更新、区間統計)

タイトルの意味は:
今、私たちはl個の数を持っていて、それから1からnとマークして、彼らの単位の長さはすべて1で、それから各単位の長さのところで私たちは1つの色しか染められません.
2つの操作があります.
「C A B C」はAを表し、B区間はCという色に染まっている.
「P A B」は質問に相当し、A、Bという区間の異なる色の数を出力する必要があります.
最初はどのように異なる色の数を求めたいのか、後でテーマの中で色の範囲が30色だと言っていることに気づいたので、ここで暴力的に列挙することができます.
この染色問題は最初はあまり分からなかったが、紙に他人のコードをシミュレートして理解した.
まず、そのノードがその区間を完全に含んでいる場合、私たちはこのノードに色をマークして、下に更新しません.これもlazy思想で、次に出会って、色が現在マークする色とは異なるまで下に更新します.
問い合わせると、一番上から探していて、1つのノードが純色であることを発見したら(つまりマークされている場合)、記録して、そのまま戻ることができます.純色は次のノードの色がこのノードの色と同じであることを示しています.それは次のノードが含まれているからです.だから最後に色を繰り返してカウントすればいいだけです.

#include
#include
#include
#include
using namespace std;
#define maxn 111111
struct node{
	int l,r,col;
}tree[maxn*4];
bool cc[55];
void build(int v,int l,int r){
	tree[v].l=l;
	tree[v].r=r;
	tree[v].col=1;
	if(l==r) return ;
	int temp=v<<1;
	int mid=(l+r)>>1;
	build(temp,l,mid);
	build(temp+1,mid+1,r);
}
void update(int v,int l,int r,int color){
	if(tree[v].l==l&&tree[v].r==r){
		tree[v].col=color;
		return;
	}
	if(tree[v].col&&tree[v].col!=color){
		int temp=v<<1;
		tree[temp].col=tree[v].col;
		tree[temp+1].col=tree[v].col;
		tree[v].col=0;
	}
	int mid=(tree[v].l+tree[v].r)>>1;
	int temp=v<<1;
	if(r<=mid) update(temp,l,r,color);
	else if(l>mid) update(temp+1,l,r,color);
	else{
		update(temp,l,mid,color);
		update(temp+1,mid+1,r,color);
	}
}
void query(int v,int l,int r){
 	if(tree[v].col>0){
		cc[tree[v].col]=true;
		return ;
	}
	int mid=(tree[v].l+tree[v].r)>>1;
	int temp=v<<1;
	if(r<=mid) query(temp,l,r);
	else if(l>mid) query(temp+1,l,r);
	else{
		query(temp,l,mid);
		query(temp+1,mid+1,r);
	}
}
int main(){
	int L,T,O;
	char ss[4];
	scanf("%d%d%d",&L,&T,&O);
	build(1,1,L);
	#if 1
	while(O--){
		scanf("%s",ss);
		int a,b,c;
		if(ss[0]=='C'){
			scanf("%d%d%d",&a,&b,&c);
			update(1,a,b,c);
		}	
		else if(ss[0]=='P'){
			int ans=0;
			fill(cc,cc+55,false);
			scanf("%d%d",&a,&b);
			query(1,a,b);
			for(int i=1;i<=T;i++){
				if(cc[i]) ans++;
			}
			printf("%d
",ans);
		}
	}
	#endif
}
/*
8 5 4
C 5 6 1
C 5 5 3
C 6 6 4
P 5 6
*/

考え方は大体こうです.
考え方:
この問題はpoj 2528のポスターに似ていて、色を塗る問題です.これまでpoj 2528をしていたときはこの考えを知らず、コードの理解も徹底していなかった.この問題をした後、Lazy-Tag思想をもっと深く理解しました.
 
線分の木を1本作った後、上に色を塗ります.塗装の問題は、次の手順に分けられます.
1.現在の区間が染色されていて、その色が染めたい色と同じである場合は、直接終了します(この文は省略できます).
2.現在の区間が染色したい区間で完全に覆われている場合、現在の区間のサブ区間も覆われている場合、その色を直接現在の区間に染めて終了する.
3.完全に覆われていない場合は、まず左右のサブツリーを現在の区間の色に染め、次に現在の区間の色を混合色0に割り当て、左右のサブツリーを再帰的に染色する.
このように完全に覆われた区間を修正すると,左右のサブツリーを遍歴することなく直接修正することができ,完全に覆われていない区間については,まずその色を左右のサブツリーに伝え,再帰的に修正し,サブツリーの色の正確性を保証した.時間の複雑さを大幅に低減した.
 
区間統計ではmark配列を設定し、ある色が現れるかどうかをマークします.1つの区間に赤が塗られている場合、この区間のどのサブ区間にも赤が塗られており、markは1と表記されており、下に遍歴する必要はありません.ブレンドカラー(0)の場合は、サブツリーを巡り続けます.最後にmark値が1の個数を統計すればよい.この人が書いたものをお勧めします.http://www.2cto.com/kf/201402/277917.html