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
题意:给定长度为n的墙，有O次操作，c a b d 代表将区间[a,b]染成颜色d,p a b 代表询问区间[a,b]有几种颜色，墙初始颜色为1，颜色种类小于等于30
很明显这是一个线段树区间修改区间查询的题目，但是问题要求询问区间内有多少种颜色，如果将区间的数依次查询记录，时间复杂度为o*nlogn，肯定会超时，
考虑到颜色的数量小于等于30，可以采用二进制的思想，线段树的每一个节点维护一个数，该数的二进制表示中1则代表有这种颜色，pushup时更新为左右两个子节点
或运算的值
AC代码:
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> using namespace std; const int maxn=1e5+5; int tree[4*maxn]; int lazy[4*maxn]; void pushup(int root) { tree[root]=tree[root<<1]|tree[root<<1|1]; } void pushdown(int root) { if(lazy[root]) { lazy[root<<1]=lazy[root]; lazy[root<<1|1]=lazy[root]; tree[root<<1]=lazy[root]; tree[root<<1|1]=lazy[root]; lazy[root]=0; } } void build(int root,int l,int r) { if(l==r) { tree[root]=1; return; } int mid=l+r>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); pushup(root); } void update(int root,int l,int r,int ql,int qr,int bit) { if(ql<=l&&qr>=r) { lazy[root]=1<<(bit-1); tree[root]=1<<(bit-1); return; } pushdown(root); int mid=l+r>>1; if(mid>=ql) update(root<<1,l,mid,ql,qr,bit); if(qr>mid) update(root<<1|1,mid+1,r,ql,qr,bit); pushup(root); } int query(int root,int l,int r,int ql,int qr) { if(l>=ql&&r<=qr) { return tree[root]; } pushdown(root); int mid=l+r>>1; int ans=0; if(mid>=ql) ans|=query(root<<1,l,mid,ql,qr); if(qr>mid) ans|=query(root<<1|1,mid+1,r,ql,qr); return ans; } int main() { int n,m,q; scanf("%d%d%d",&n,&m,&q); build(1,1,n); while(q--) { char opt; scanf(" %c",&opt); if(opt==‘C‘) { int l,r,c; scanf("%d%d%d",&l,&r,&c); if(l>r) swap(l,r); update(1,1,n,l,r,c); } else { int l,r; scanf("%d%d",&l,&r); if(l>r)//输入的l可能大于r,特判一下 swap(l,r); int temp=query(1,1,n,l,r); int ans=0; while(temp>0) { ans+=temp%2; temp/=2; } printf("%d\n",ans); } } return 0; }
原文：https://www.cnblogs.com/aaddvvaanntteezz/p/10809433.html