1100: [视频]线段树2（统计不同颜色）
题目描述
【题目描述】有L段线段（编号为1～L， (1 <= L <= 1000000)），一开始全部线段是颜色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行操作
【输出】：有询问的时候输出
Sample Input
2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
Sample Output
2
1
虽然说这题oj上面有标解还有标解的代码。。
但是昨天标解被hack了
方法就是将他的序列刚好弄成1,2,1,2,1,2,1,2，那么他的c就几乎没有任何用处了。。
换句活说，标解就是一个暴力+玄学优化。。
数据水的话能过。。但是要是上面这个的话，就被卡成O(n2)了。。
据说跑了几十秒才跑出来，超时到爆炸。。
于是就开始思考有没有更好的方法。。
一开始想的是待修改的莫队，然而这个复杂度肯定过不去
那么还是回归线段树吧
我们考虑对序列的每一个点都建一个bitset，不会的点这里，然后维护就是两个bitset或一下就好了。。
由于是一段修改，于是我们要打lazy，不打会T
时间复杂度的话是O(nlogn*50/32)，感觉这个复杂度就可以过了吧。。至少比标解靠谱很多。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000005;
struct qq
{int l,r;int s1,s2;bitset<51> c;int lazy;
}s[N*2];int num=0;
int l,m;
void bt (int l,int r)
{int a=++num;s[a].l=l;s[a].r=r;s[a].lazy=0;s[a].c.reset();s[a].c[1]=1;if (l==r) return ;int mid=(l+r)>>1;s[a].s1=num+1;bt(l,mid);s[a].s2=num+1;bt(mid+1,r);
}
void update (int x)
{int s1=s[x].s1,s2=s[x].s2;int lazy=s[x].lazy;s[x].lazy=0;s[s1].c.reset();s[s1].c[lazy]=1;s[s1].lazy=lazy;s[s2].c.reset();s[s2].c[lazy]=1;s[s2].lazy=lazy;return ;
}
void change (int now,int l,int r,int tt)//这一段范围都变成这个
{if (s[now].l==l&&s[now].r==r){s[now].c.reset();s[now].c[tt]=1;s[now].lazy=tt;return ;}if (s[now].lazy!=0) update(now);int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) change(s1,l,r,tt);else if (l>mid) change(s2,l,r,tt);else change(s1,l,mid,tt),change(s2,mid+1,r,tt);s[now].c=(s[s[now].s1].c|s[s[now].s2].c);return ;
}
bitset<51> ans;
void solve (int now,int l,int r)
{if (s[now].l==l&&s[now].r==r){ans=(ans|s[now].c);return ;}if (s[now].lazy!=0)update(now);int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) solve(s1,l,r);else if (l>mid) solve(s2,l,r);else solve(s1,l,mid),solve(s2,mid+1,r);
}
int main()
{scanf("%d%d",&l,&m);bt(1,l);for (int u=1;u<=m;u++){char ss[5];scanf("%s",ss);if (ss[0]=='C'){int l,r,tt;scanf("%d%d%d",&l,&r,&tt);if (l>r) swap(l,r);change(1,l,r,tt);}else{ans.reset();int l,r;scanf("%d%d",&l,&r);if (l>r) swap(l,r);solve(1,l,r);printf("%d\n",ans.count());}}return 0;
}