时间锁链
时间限制: 1 Sec 内存限制: 128 MB
[命题人:admin] [ Edit] [ TestData]
题目描述
当墨老师找到封闭时间环中最小的逆序对数后，他就可以将时间环展开成一个长L的时间锁链（我们可以将之看成是一根很长的管子），其中L是整数，所以我们可以将该管子分为L段，并从左到右标记为1，2，…，L。
现在对管子有两种操作：
“C A B C” 将A到B的数都标记为C（我们可形象的看成是染成C这种颜色）。
“P A B” 输出A和B之间不同颜色的数目。
颜色有T种，标记为1，2，3…，T，T是一个很小的值，初始时管子的颜色为1。
输入
第一行为L (1≤L≤100 000)，T (1≤T≤30)和O (1≤O≤100 000)，其中O表示操作数。随后O行为操作命令即"C A B C"或"P A B"，其中A可能比B值大。
输出
输出操作的结果。
样例输入 Copy
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
样例输出 Copy
2
1
题意：
题意很简单，给你一个区间和两种操作，你可以更改区间的数或是查询区间里有多少种不同的数。
思路：
典型的区间修改和区间查询，用线段树维护一下就可以了。
因为颜色的总数目很小，我们可以开一个bool数组暴力记录（应该可以~），也可以把状态压缩成二进制数，表示的含义就是第i位为1时说明第i个颜色被涂上了。
代码：
注意一下pushdown的写法~
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7; struct node{ int l,r; int sum;//二进制表示涂了多少种颜色 int lazy; }a[maxn]; void pushdown(int u){ if(a[u].lazy){ a[u<<1].lazy=a[u<<1|1].lazy=a[u].lazy; a[u<<1].sum=a[u<<1|1].sum=(1<<a[u].lazy); a[u].lazy=0; } } void build(int u,int l,int r){ a[u].l=l;a[u].r=r; if(l==r) a[u].sum=1<<1; else{ int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); a[u].sum=a[u<<1].sum|a[u<<1|1].sum; } } void update(int u,int z,int l,int r){ if(a[u].l>r||a[u].r<l) return ;///完全不包含 if(a[u].l>=l&&a[u].r<=r){//完全包含 a[u].sum=1<<z; a[u].lazy=z; return ; } pushdown(u); update(u<<1,z,l,r);update(u<<1|1,z,l,r); a[u].sum=a[u<<1].sum|a[u<<1|1].sum; } int query(int u,int l,int r){ if(a[u].l>r||a[u].r<l) return 0; if(a[u].l>=l&&a[u].r<=r) return a[u].sum; pushdown(u); return query(u<<1,l,r)|query(u<<1|1,l,r); } int main(){ int n,t,o; cin>>n>>t>>o; build(1,1,n); while(o--){ char op;int x,y; cin>>op>>x>>y; if(op=='P'){ if(x>y) swap(x,y); int res=query(1,x,y); int sum=0; for(int i=1;i<=t;i++) if(res&(1<<i)) sum++; cout<<sum<<endl; } else if(op=='C'){ int z; if(x>y) swap(x,y); cin>>z; update(1,z,x,y); } } return 0; }
