#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=100000;
struct node
{
	int left,right,cover;
};
node tree[MAX*3];
bool used[31];
void built(int L,int R,int id)//建树
{
	tree[id].cover=1;//初始化颜色
	tree[id].left=L;
	tree[id].right=R;
	if(L<R)
	{
		int mid=(L+R)/2;
		built(L,mid,2*id); //左子树
		built(mid+1,R,2*id+1); //右子树
	}
}
void insert(int id,int L,int R,int col)
{
	if(tree[id].left>=L&&tree[id].right<=R)
	{
		tree[id].cover=col;
		return;
	}
	if(tree[id].left<tree[id].right)
	{
		int mid=(tree[id].left+tree[id].right)>>1;
		if(tree[id].cover>0)
		{
			tree[id*2].cover=tree[id].cover;
			tree[id*2+1].cover=tree[id].cover;
		}
		tree[id].cover=-1;
		if(R<=mid)
			insert(id*2,L,R,col);
		else if(L>mid)
			insert(id*2+1,L,R,col);
		else
		{
			insert(id*2,L,mid,col);
			insert(id*2+1,mid+1,R,col);
		}
	}
}
void cnt(int L,int R,int id)
{
	if(tree[id].cover>0)
	{
		used[tree[id].cover]=true;
		return;
	}
	if(tree[id].left<tree[id].right)
	{
		int mid=(tree[id].left+tree[id].right)>>1;
		if(R<=mid)
			cnt(L,R,id*2);
		else if(L>mid)
			cnt(L,R,id*2+1);
		else
		{
			cnt(L,mid,id*2);
			cnt(mid+1,R,id*2+1);
		}
	}
}
int main()
{
	int L,T,Q;
	scanf("%d %d %d",&L,&T,&Q);
	int i,x,y,c;
	built(1,L,1);
	while(Q--)
	{
		char ch[2];
		scanf("%s",ch);
		if(ch[0]=='C')
		{
			scanf("%d %d %d",&x,&y,&c);
			if(x<=y)
				insert(1,x,y,c);
			else
				insert(1,y,x,c);
		}
		else
		{
			scanf("%d %d",&x,&y);
			memset(used,false,sizeof(used));
			if(x<=y)
				cnt(x,y,1);
			else
				cnt(y,x,1);
			int ans=0;
			for(i=1;i<=T;i++)
			if(used[i])ans++;
			printf("%d\n",ans);
		}
	}
	return 0;
}

• Re:线段树......................................贴代码................................................ (22) daoershuai 2011-09-01 23:36:37
  • 我看了……………………………………………… (0) 5D6D2 2012-07-16 11:15:32