| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 44503 | Accepted: 13494 |
Description
Input
Output
Sample Input
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2
Sample Output
2 1
题目大意：有一块木板分为许多段，它们开始的时候是同一个颜色，现在有两种操作:1.将区间$[l,r]$涂成一种颜色。2.询问区间$[l,r]$中共有多少种不同的颜色。
这看起来就像一道线段树的题(其实它本身也是)，但是它与其它题目最不同的地方就在于对颜色状态的记录，如果单纯用加法去将每段区间内不同的颜色加起来，这个想法似乎比较对，但是在实现上会有障碍，因为我们不方便记录下到底有多少种不同的颜色，在统计时就会遇到障碍。于是我们可以会有一种奇怪的想法：可不可以用二进制串来描述每个区间涂色的状态呢(其实这也是套路)？答案当然是可以的，我们可设一个二进制串它的第$i$位表示第$i$种颜色是否在这个区间上，例如0011表示该区间中1号和2号颜色都被填涂了。那么我们就可以用位运算来处理状态了。在将子节点的信息分布给根节点时只有$or$一下就行了。最后查找答案时得到的也是一个二进制串，我们只要统计二进制串中的1就可以了。
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; static const int maxm=1e6+10; int tr[maxm],lz[maxm],left[maxm],right[maxm]; void build(int num,int l,int r){ left[num]=l;right[num]=r; if(l==r){tr[num]=1;return;} int mid=(l+r)>>1; build(num<<1,l,mid); build(num<<1|1,mid+1,r); tr[num]=tr[num<<1]|tr[num<<1|1]; } void pushdown(int num){ if(lz[num]){ tr[num<<1]=tr[num];tr[num<<1|1]=tr[num]; lz[num<<1]=1;lz[num<<1|1]=1; lz[num]=0; } } void update(int num,int l,int r,int val){ if(left[num]>=l&&right[num]<=r){ lz[num]=1;tr[num]=val; return; } if(left[num]>r||right[num]<l)return; pushdown(num); update(num<<1,l,r,val); update(num<<1|1,l,r,val); tr[num]=tr[num<<1]|tr[num<<1|1]; } int Query(int num,int l,int r){ if(left[num]>=l&&right[num]<=r)return tr[num]; if(left[num]>r||right[num]<l)return 0; int ret=0;pushdown(num); ret|=Query(num<<1,l,r);ret|=Query(num<<1|1,l,r); return ret; } int main(){ int n,t,m; while(scanf("%d%d%d",&n,&t,&m)!=EOF){ build(1,1,n); while(m--){ char s[5]; scanf("%s",s); if(s[0]==‘C‘){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a>b)swap(a,b); update(1,a,b,1<<(c-1)); }else{ int a,b,ans=0; scanf("%d%d",&a,&b); int sum=Query(1,a,b); while(sum){ if(sum&1)ans++; sum>>=1; } printf("%d\n",ans); } } } return 0; }
AC通道：http://poj.org/problem?id=2777
原文：http://www.cnblogs.com/Exbilar/p/6389258.html
