count color(poj区间颜色数，线段树).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
	int l,r;
	node * pl, * pr;
	int col;
	int dif;
}mem[250000];
int mem_pos;

node *
new_node()
{
	node * pt = &mem[mem_pos ++];
	memset(pt,0,sizeof(pt));
	pt ->col = pt ->dif = 1;
	return pt;
}

node *
make_tree(int l,int r)
{
	node * root = new_node();
	root ->l = l;
	root ->r = r;
	if(r - l > 1) {
		int mid = (l+r)/2;
		root ->pl = make_tree(l,mid);
		root ->pr = make_tree(mid,r);
	}
	return root;
}

void
update(node * root, int l,int r, int c)
{
	if(root ->col > 0) {//color branch
		if(root ->pl) {
			root ->pl ->col = root ->pl ->dif = root ->col;
		}
		if(root ->pr) {
			root ->pr ->col = root ->pr ->dif = root ->col;
		}
	}

	if(root ->col != 1<<(c-1)) {
		root ->col = 0;//mixed color
	}
	
	if(root ->l == l && root ->r == r) {
		root ->col = root ->dif = 1<<(c-1);//cover color
		return ;
	}

	if(root ->pl ->r > l) {
		if(root ->pl ->r >= r) {
			update(root ->pl,l,r,c);
		}
		else {
			int mid = (root ->l + root ->r)/2;
			update(root ->pl,l,mid,c);
			update(root ->pr,mid,r,c);
		}
	}
	else {
		update(root ->pr,l,r,c);
	}

	root ->dif = root ->pl ->dif | root ->pr ->dif;
}

int
find(node * root, int l,int r)
{
	if(root ->col > 0) {
		return root ->col;
	}
	if(root ->l == l && root ->r == r) {
		return root ->dif;
	}
	if(root ->pl ->r > l) {
		if(root ->pl ->r >= r) {
			return find(root ->pl,l,r);
		}
		else {
			int mid = (root ->l + root ->r)/2;
			int c1 = find(root ->pl,l,mid);
			int c2 = find(root ->pr,mid,r);
			return c1 | c2;
		}
	}
	else {
		return find(root ->pr,l,r);
	}
}

int
main()
{
	int i,j,l,t,o;
	int a,b,c;
	mem_pos = 0;
	node * root = make_tree(0,100000);
	while(scanf("%d %d %d",&l,&t,&o)==3) {
		for(i=0;i<mem_pos;i++) {
			mem[i].col = mem[i].dif = 1;
		}
		char cmd[5];
		while(o --) {
			getchar();
			scanf("%s",cmd);
			if(cmd[0] == 'C') {
				scanf("%d %d %d",&a,&b,&c);
				if(a > b) {
					swap(a,b);
				}
				update(root,a-1,b,c);
			}
			else if(cmd[0] == 'P') {
				scanf("%d %d",&a,&b);
				if(a > b) {
					swap(a,b);
				}
				int col = find(root,a-1,b);
				int count = 0;
				for(i=0;i<t;i++) {
					if(col & 1<<i) {
						count ++;
						//printf("color %d\n",i+1);
					}
				}
				printf("%d\n", count);
			}
		}
	}
}