Poj 2777 Count Color

제목: n 길이 의 선분 (n < 1000000) 과 t 가지 물감 (t < 30) 을 드 립 니 다. 다음 두 가지 조작 이 있 습 니 다.          C a b c: a 에서 b 까지 의 선분 에 c 색 을 칠 합 니 다.
          P a b: a 에서 b 까지 의 선분 에 몇 가지 색상 이 있 는 지 물 어 봅 니 다.
사고방식: 라인 트 리 의 응용, 그리고 하나의 라인 트 리 가 자주 사용 하 는 사고방식 인 레이 지 를 사 용 했 습 니 다. 레이 지 는 말 그대로 게 으 름 입 니 다. 이것 은 업 데 이 트 를 할 때 모든 라인 에 업데이트 할 필요 가 없다 는 것 을 말 합 니 다.

#include 
using namespace std;
#include 
#include 
#include 
const int MAXN = 100005;
const int COLOR_NUM=35;
const int DEFAULT_COLOR=0;

struct node {
	int left;
	int right;
	int color;
};
node tree[MAXN*5];
bool visit[COLOR_NUM];
int l;

void build(const int &left, const int &right, const int &node_num=1) {
	tree[node_num].left=left;
	tree[node_num].right=right;
	tree[node_num].color=DEFAULT_COLOR;

	if (left==right)
		return;
	int mid = (left+right) >> 1;
	build(left,mid,2*node_num);
	build(mid+1,right,2*node_num+1);
}
void init() {
	build(1,l);
	tree[1].color=1;
}
void insert(const int &left, const int &right, const int &color, const int &node_num = 1 ) {
	if (left==tree[node_num].left&&right==tree[node_num].right) {
		tree[node_num].color=color;
		return;
	}
	if (tree[node_num].color!=DEFAULT_COLOR) {
		tree[node_num*2].color=tree[node_num].color;
		tree[node_num*2+1].color=tree[node_num].color;
		tree[node_num].color=DEFAULT_COLOR;
	}
	int mid=(tree[node_num].left+tree[node_num].right) >> 1;
	if (right<=mid) 
		insert(left,right,color,node_num*2);
	else if (left>mid) 
		insert(left,right,color,node_num*2+1);
	else {
		insert(left,mid,color,node_num*2);
		insert(mid+1,right,color,node_num*2+1);
	}
}

int query(const int &left, const int &right, const int &node_num=1) {
	int ctr=0;
	if (tree[node_num].color!=DEFAULT_COLOR) {
		if (visit[tree[node_num].color]==false) {
			ctr++;
			visit[tree[node_num].color]=true;
		}
		return ctr;
	}
	int mid = (tree[node_num].left+tree[node_num].right) >> 1;
	if (right<=mid)
		ctr+=query(left,right,node_num*2);
	else if (left>mid)
		ctr+=query(left,right,node_num*2+1);
	else {
		ctr+=query(left,mid,node_num*2);
		ctr+=query(mid+1,right,node_num*2+1);
	}
	return ctr;
} 
int main()
{
	int t,o,i;
	char operation;
	int a,b,c,temp;

	scanf("%d%d%d",&l,&t,&o);
	init();

	while (o--) {
		getchar();
		scanf("%c",&operation);
		if (operation=='C') {
			scanf("%d%d%d",&a,&b,&c);
			if (a>b) {
				temp=a;
				a=b;
				b=temp;
			}
			insert(a,b,c);
		}
		else {
			scanf("%d%d",&a,&b);
			if (a>b) {
				temp=a;
				a=b;
				b=temp;
			}
			memset(visit,false,sizeof(visit));
			printf("%d
",query(a,b));
		}
	}
	return 0;
}