华师一附中OI组

标题: 线段树模板统计不同颜色 [打印本页]

作者: admin 时间: 2018-5-13 01:01
标题: 线段树模板统计不同颜色
【题意】
有L段线段（编号为1～L， (0 <= L <= 1000000)），一开始全部线段是颜色1。
有两种操作：
1、C A B tt ：把第A至第B个线段染成第tt种颜色
2、P A B ：询问第A至第B个线段有多少种不一样的颜色。
注意：
1、A有可能比B大。
2、颜色的编号<=50;
数据较水，不用担心特殊的情况，按照题解打也能AC，数据强的版本已放在1238
【输入格式】
第一行含有三个整数 L and M (1 <= M <= 100000). M代表操作次数. 下来M行操作
【输出格式】
有询问的时候输出
【样例输入】
2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
【样例输出】
2
1

作者: admin 时间: 2018-5-13 01:01
算法思路：
第一题中修改的是一个点，现在修改的是一段，不用线段树，修改也会超时
统计一段里面颜色的种数，也是得用线段树，不然也会超时。
所以这道题体现线段树更加彻底。
这一题的c我们运用一个新东西叫做bitset
需要的头文件
#include<bitset>
定义方法
bitset<你要的大小> bi
赋值
直接像变量一样用就好了
a[x]=1或a[x]=0
与bool的巨大区别
可以用一切运算符，想<<,>>,^,|,&等，和二进制一样
一些常用的函数
bool any( )
是否存在置为1的二进制位？和none()相反
bool none( )
是否不存在置为1的二进制位,即全部为0？和any()相反.
size_t count( )
二进制位为1的个数.
size_t size( )
二进制位的个数
flip()
把所有二进制位逐位取反
set()
把所有二进制位都置为1
set(pos)
把在pos处的二进制位置为1
reset()
把所有二进制位都置为0
count()
获得由多少个1
那么统计颜色怎么办？全局用一个ans，一有颜色就加进ans当中，最后直接count即可。
输入

作者: admin 时间: 2018-5-13 01:03
加强版  1 <= L <= 1 0000 0000 那就必须离散化了

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);

欢迎光临华师一附中OI组 (http://hsyit.cn/)