【题意】
有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

 

《离散化》by scy

1、什么是离散化？比如:
原数组为A[]={3,100,9845587},
离散化为S[]={1,2,3}
S[i]的值：A[i]在A数组排老几。

再比如：
原数组为A[]={ 3 , 100 , 9845587 , 6 , 6 , 9 , 11 , 2 },
离散化为S[]={ 2 ,  6  ,   7   , 3 , 3 , 4 ,  5 , 1 }

2、离散化的过程：

   1：原数组A每个数还得多带点东西：它原来在A数组的位置
   2：把A复制一份为B，然后B数组根据B中x的值进行排序，然后根据B排序后的位置赋予每个B的离散值
   3：让B中的每个元素带着自己的离散值和位置值去建造s数组。s[  B.p ] = B.z ;
   4：到此离散化结束，S的每个元素的值就是原来A数组每个元素的离散值，而且一一对应。

具体离散化的代码：
struct LSnode//离散化用的结构体
{
    int x,z,p;//x表示原来的值，z表示离散化后的值，p表示x在原来数组A中的位置
}A[21000],B[21000];

int s[21000];//s[i]的值：就是A[i].x在A数组排老几

int cmp(LSnode n1,LSnode n2)
{
     return n1.x<n2.x;
}

for(i=1;i<=n;i++)
{
    scanf("%d%d",&A[2*i-1].x,&A[2*i].x);// A[1]和A[2]是一对，A[3]和A[4]是一对~~~~~~~
    A[2*i-1].p=2*i-1;
    A[2*i  ].p=2*i;
}

for(i=1;i<=n;i++){ B[i].x=A[i].x;B[i].p=A[i].p;}//B就是A的复制
sort(B+1,B+2*n+1,cmp);//把B根据B.x的值进行从小到大排序

B[1].z =1;//第一的离散值为1

//如果B[i].x和前面一个相等，那么离散值也相等，否则离散值等于前面一个的离散值+1

for(i=2;i<=2*n;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(i=1;i<=2*n;i++)  s[ B[i].p ]  =  B[i].z;// 从此s就是浓缩的A数组,怎么说？ A[1].x和A[2].x离散化后的值就是s[1]和s[2]

接下来的事情就是

len=0;bt( 1 ,  B[2*n].z );
for(int i=1;i<=n;i++) change(1,s[2*i-1],s[2*i],i);//本来是要写 change(1,A[2*i-1].x,A[2*i].x,i);
memset(v,false,sizeof(v));
wen(1 , 1, B[2*n].z );
ans=0;for(i=1;i<=n;i++) if( v[i]==true) ans++;
printf("%d\n",ans);

其他代码自己补充完整