poj - 2777 - Count Color（线段树）

题意：长为L的区间，初始每个单位区间都为颜色1，执行两种操作，C A B C，将区间[A, B]染为颜色C，P A B，询问区间A, B]有多少种颜色（1 <= L <= 100000, 1 <= 颜色T <= 30）。

题目链接：http://poj.org/problem id=2777

――>>不错的题目，因为颜色的各类只有30种，所以每种颜色可以用1移位来表示，设col[o]表示线段树结点o的颜色状态，那么col[o]的低30位有多少个1就表示有多少种颜色。。。#^_^

#include 
  
   
#include 
   
     using namespace std; #define lc (o<<1) #define rc ((o<<1)+1) const int maxn = (100000 + 10) << 2; bool one[maxn]; //是否为单一色 int col[maxn], sum; void build(int o, int l, int r) { col[o] = 1; //初始为颜色1 one[o] = true; //是单一色 if(l == r) return; int m = (l + r) >> 1; build(lc, l, m); build(rc, m+1, r); } void pushdown(int o) { col[lc] = col[rc] = col[o]; one[lc] = one[rc] = true; one[o] = false; } void update(int o, int l, int r, int ql, int qr, int v) { if(ql <= l && r <= qr) { col[o] = v; one[o] = true; return; } if(col[o] == v) return; if(one[o]) pushdown(o); int m = (l + r) >> 1; if(ql <= m) update(lc, l, m, ql, qr, v); if(qr > m) update(rc, m+1, r, ql, qr, v); col[o] = col[lc] | col[rc]; } void query(int o, int l, int r, int ql, int qr) { if((ql <= l && r <= qr) || one[o]) { sum |= col[o]; return; } int m = (l + r) >> 1; if(ql <= m) query(lc, l, m, ql, qr); if(qr > m) query(rc, m+1, r, ql, qr); } int solve() { int ret = 0; for(int i = 0; i < 30; i++) if((1<
    
      B) swap(A, B); update(1, 1, L, A, B, 1<<(C-1)); } else { sum = 0; scanf("%d%d", &A, &B); if(A > B) swap(A, B); query(1, 1, L, A, B); printf("%d\n", solve()); } } } return 0; }