线段树模板 poj2777

线段数涂色

#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100005
struct node
{
	int left,right;
	int color;
}tree[maxn*4];
bool visit[40];
int sum;
void build(int left,int right,int id)
{
	tree[id].left =left,tree[id].right =right;
	if(left==right)
	{
		tree[id].color =1;
		return;
	}
	tree[id].color =1;
	int mid=(left+right)>>1;
	build(left,mid,id*2);
	build(mid+1,right,id*2+1);
}

void insert(int st,int ed,int color,int id)
{
	if(tree[id].left ==st&&tree[id].right==ed)
	{
		tree[id].color =color;
		return;
	}
	if(tree[id].color)
	{
		tree[id*2].color =tree[id].color;
		tree[id*2+1].color =tree[id].color ;
		tree[id].color =0;
	}
	//tree[id].color =0;
	int mid=(tree[id].left +tree[id].right )>>1;
	if(mid>=ed)
		insert(st,ed,color,id*2);
	else if(mid<st)
		insert(st,ed,color,id*2+1);
	else
	{
		insert(st,mid,color,id*2);
		insert(mid+1,ed,color,id*2+1);
	}
}
void query(int st,int ed,int id)
{
	if(tree[id].color)
	{
		if(!visit[tree[id].color ])
		{
			sum++;
			visit[tree[id].color]=true;
		}
		return;
	}
	int mid=(tree[id].left +tree[id].right )>>1;
	if(mid>=ed)
		query(st,ed,id*2);
	else if(mid<st)
		query(st,ed,id*2+1);
	else
	{
		int mid=(tree[id].left +tree[id].right )>>1;
		query(st,mid,id*2);
		query(mid+1,ed,id*2+1);	
	}
}

int main()
{
	char ch[5];
	int L,T,O,a,b,c;
	scanf("%d%d%d",&L,&T,&O);	
	build(1,L,1);
	while(O--)
	{
		scanf("%s",&ch);
		scanf("%d%d",&a,&b);
		if(a>b)
		swap(a,b);
		if(ch[0]=='C')
		{
			scanf("%d",&c);
			insert(a,b,c,1);
		}
		else if(ch[0]=='P')
		{
			sum=0;
			memset(visit,0,sizeof(visit));
			query(a,b,1);
			printf("%d\n",sum);
		}
	}
	return 0;
}