題目鏈接：[點擊打開鏈接](http://poj.org/problem?id=2777) 題意：兩種操作， 一個是區間修改， 一個是區間查詢顏色種類數。 該題因為要不斷的求某個區間的顏色種類數， 我們可以用位運算的并來實現。 其他的就是線段樹區間修改的經典操作了。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,t,q,l,r,c,sum[maxn<<2],setv[maxn<<2]; void PushUp(int o) { sum[o] = sum[o<<1] | sum[o<<1|1]; } void pushdown(int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; sum[o<<1] = sum[o<<1|1] = (1<<setv[o]); setv[o] = 0; } } void build(int l, int r, int o) { int m = (l + r) >> 1; setv[o] = 0; sum[o] = (1<<1); if(l == r) return ; build(l, m, o<<1); build(m+1, r, o<<1|1); } void update(int L, int R, int c, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { sum[o] = (1 << c); setv[o] = c; return ; } pushdown(o); if(L <= m) update(L, R, c, l, m, o<<1); if(m < R) update(L, R, c, m+1, r, o<<1|1); PushUp(o); } int query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(o); int ans = 0; if(L <= m) ans |= query(L, R, l, m, o<<1); if(m < R) ans |= query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } char s[10]; int main() { scanf("%d%d%d",&n, &t, &q); build(1, n, 1); while(q--) { scanf("%s",s); if(s[0] == 'C') { scanf("%d%d%d",&l, &r, &c); update(min(l,r), max(l,r), c, 1, n, 1); } else { scanf("%d%d",&l, &r); int ans = query(min(l,r), max(l,r), 1, n, 1), cnt = 0; for(int i=1;i<=t;i++) { if(ans & (1<<i)) ++cnt; } printf("%d\n",cnt); } } return 0; } ~~~