题目：

1101: [视频]线段树3（统计不同颜色加强版）
时间限制: 1 Sec  内存限制: 128 MB
提交: 592  解决: 260
[提交][状态][讨论版]
题目描述
【题意】
有L段线段（编号为1～L， (1 <= L <= 1 0000 0000   没错，就是1亿 )） ，一开始全部线段是颜色1。
有两种操作：
1、C A B tt ：把第A至第B个线段染成第tt种颜色
2、P A B ：询问第A至第B个线段有多少种不一样的颜色。
注意：
1、A有可能比B大。
2、颜色的编号<=50;
【输入格式】
第一行含有两个整数 L and M (1 <= M <= 100000).  M代表操作次数. 下来M行操作
【输出格式】
有询问的时候输出
【样例输入1】
2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
【样例输出1】
2
1
【样例输入2】

10 3
C 1 2 2
C 4 10 3
P 1 10

【样例输出2】

3

要用离散化

我的代码：

#include<bits/stdc++.h>
using namespace std;
struct aaa
{
	int l,r,lc,rc,c;
}tr[2100000];
struct sma
{
	int x,z,p;
}a[210000],b[210000];
bool v[200001];
int s[210000];
int l,m;
int len;
int cmp(sma x,sma y)
{
	return x.x<y.x;
}
int build(int l,int r)
{
	len++;
	int now=len;
	tr[now].l=l;
	tr[now].r=r;
	tr[now].lc=tr[now].rc=-1;
	if(l==r) tr[l].c=1;
	else
	{
		int mid=(l+r)/2;
		tr[now].lc=len+1;
		build(l,mid);
		
		tr[now].rc=len+1;
		build(mid+1,r);
	}
}
void change(int now,int l,int r,int k)
{
	if(tr[now].c==k) return ;
	if(tr[now].l==l&&tr[now].r==r)
	{
		tr[now].c=k;
		return ;
	}
	int lc=tr[now].lc,rc=tr[now].rc;
	int mid=(tr[now].l+tr[now].r)/2;
	if(tr[now].c>0)
	{
		tr[lc].c=tr[now].c;
		tr[rc].c=tr[now].c;
	}
	if(r<=mid) change(lc,l,r,k);
	else if(l>=mid+1) change(rc,l,r,k);
	else 
	{
		change(lc,l,mid,k);
		change(rc,mid+1,r,k);
	}
	if(tr[lc].c==tr[rc].c&&tr[lc].c>0) tr[now].c=tr[lc].c;
	else tr[now].c=-1;
	
}
void wen(int now,int l,int r)
{
	if(tr[now].c>0)
	{
		v[tr[now].c]=1;
		return ;
	}
	int lc=tr[now].lc,rc=tr[now].rc;
	int mid=(tr[now].l+tr[now].r)/2;
	if(r<=mid) wen(lc,l,r);
	else if(l>=mid+1) wen(rc,l,r);
	else
	{
		wen(lc,l,mid);
		wen(rc,mid+1,r);
	}
	
}
int main()
{
//	freopen("colour.in","r",stdin);
//	freopen("colour.out","w",stdout);
	scanf("%d%d",&l,&m);
	char c[210000];
	int k[210000];
	for(int i=1;i<=m;i++)
	{
		cin>>c[i];
		scanf("%d%d",&a[i*2-1].x,&a[i*2].x);
		if(c[i]=='C') cin>>k[i];
		a[i*2-1].p=i*2-1;
		a[i*2].p=i*2;
	}
	for(int i=1;i<=m*2;i++)
	{
		b[i].x=a[i].x;
		b[i].p=a[i].p;
	}
	sort(b+1,b+1+2*m,cmp);
	b[1].z=1;
	for(int i=2;i<=2*m;i++)
	{
		if(b[i].x==b[i-1].x) b[i].z=b[i-1].z;
		else b[i].z=b[i-1].z+1;
	}
	for(int i=1;i<=2*m;i++)
	{
		s[b[i].p]=b[i].z;
	}	
	len=0;
	build(1,b[2*m].z);
	tr[1].c=1;
	for(int i=1;i<=m;i++)
	{
		int x=s[i*2-1],y=s[i*2];
		if(c[i]=='C')
		{
			if(x>y) swap(x,y);
			change(1,x,y,k[i]);
		}
		if(c[i]=='P')
		{
			if(x>y) swap(x,y);
			memset(v,0,sizeof(v));
			wen(1,x,y);
			int ans=0;;
			for(int j=1;j<=m;j++) if(v[j]) ans++;
			cout<<ans<<endl;
		}
	}
	return 0;
}