POJ 2777 - Count Color（線段樹區間更新+狀態壓縮）

題目鏈接 https://cn.vjudge.net/problem/POJ-2777

【題意】
有一個長度為 $L$ 的區間 $[1,L]$ ，有 $T$ 種顏色可以涂，有 $Q$ 次操作，操作分兩種
$CABC$ 把區間 $[A,B]$ 涂成第 $C$ 種顏色
$PAB$ 查詢區間 $[A,B]$ 有多少種不同的顏色
初始全部為第 $1$ 種顏色（L,Q&lt;=105,T&lt;=30L,Q&lt;=10^5,T&lt;=30L,Q<=105,T<=30）

【思路】
因為顏色種類比較少，所以可以用二進制來表示某個區間的顏色集合，合并時用按位或運算，用lazy標記區間更新，查詢結果中二進制里1的個數就是答案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define node tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]
using namespace std;const int maxn=100005;struct Tree{int left,right;int col,lazy;
}tree[maxn<<2];int n,m,q;void pushup(int id){node.col=lson.col|rson.col;}void pushdown(int id){if(node.lazy && node.left!=node.right){lson.lazy=node.lazy;lson.col=(1<<(node.lazy-1));rson.lazy=node.lazy;rson.col=(1<<(node.lazy-1));node.lazy=0;}
}void build(int id,int le,int ri){node.left=le;node.right=ri;node.lazy=0;if(le==ri){node.col=1;return;}int mid=(le+ri)>>1;build(id<<1,le,mid);build(id<<1|1,mid+1,ri);pushup(id);
}void update(int id,int le,int ri,int val){if(node.left==le && node.right==ri){node.col=(1<<(val-1));node.lazy=val;return;}pushdown(id);int mid=(node.left+node.right)>>1;if(ri<=mid) update(id<<1,le,ri,val);else if(le>mid) update(id<<1|1,le,ri,val);else{update(id<<1,le,mid,val);update(id<<1|1,mid+1,ri,val);}pushup(id);
}int query(int id,int le,int ri){if(node.left==le && node.right==ri){return node.col;}pushdown(id);int mid=(node.left+node.right)>>1;if(ri<=mid) return query(id<<1,le,ri);else if(le>mid) return query(id<<1|1,le,ri);else{return query(id<<1,le,mid)|query(id<<1|1,mid+1,ri);}
}int main(){while(scanf("%d%d%d",&n,&m,&q)==3){build(1,1,n);while(q--){char op[2];scanf("%s",op);if(op[0]=='C'){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a>b) swap(a,b);update(1,a,b,c);}else{int a,b;scanf("%d%d",&a,&b);if(a>b) swap(a,b);int ans=query(1,a,b);printf("%d\n",__builtin_popcount(ans));}}}return 0;
}