[关闭]
@Acqua 2018-12-21T08:06:52.000000Z 字数 1372 阅读 1789

POJ2777 Count Color（Dec. 21th, 2018）

线段树

题目来源

题意

给定长度为的序列、种颜色，个操作，要求把内的所有数染成第种颜色，要求求出内颜色种数。

思路

因为只有30种颜色，所以用二进制标记颜色。
线段树数组中存储以为根节点的树所维护的区间中颜色的二进制或 Or值。

反思

更新不要顾头不顾尾。物理中有一种计算压强的方法，叫做液片法。写程序同理，要从更新过程中取一个断点，研究它的值的来源和目的地，借此构建递归方法。

代码

  1. // La Lune
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. #define N 100005
  7. #define root 1, 1, n
  8. #define lr u << 1
  9. #define rr u << 1 | 1
  10. #define lson lr, l, mid
  11. #define rson rr, mid + 1, r
  12. #define base int u, int l, int r
  13. using namespace std;
  14. int t[N << 2], lz[N << 2];
  15. void build(base){
  16.     t[u] = lz[u] = 0;
  17.     if(l == r){
  18.         t[u] = 1;
  19.         return;
  20.     }
  21.     int mid = l + r >> 1;
  22.     build(lson);
  23.     build(rson);
  24.     t[u] = t[lr] | t[rr];
  25. }
  26. void pushdown(int u){
  27.     if(lz[u]){
  28.         lz[lr] = lz[rr] = lz[u];
  29.         t[lr] = t[rr] = t[u];
  30.         lz[u] = 0;
  31.     }
  32. }
  33. void update(base, int a, int b, int c){
  34.     if(a <= l && r <= b){
  35.         t[u] = lz[u] = (1 << (c - 1));
  36.         return;
  37.     }
  38.     pushdown(u);
  39.     int mid = l + r >> 1;
  40.     if(a <= mid)
  41.         update(lson, a, b, c);
  42.     if(b > mid)
  43.         update(rson, a, b, c);
  44.     t[u] = t[lr] | t[rr];
  45. }
  46. int query(base, int a, int b){
  47.     if(a <= l && r <= b)
  48.         return t[u];
  49.     pushdown(u);
  50.     int mid = l + r >> 1;
  51.     int res = 0;
  52.     if(a <= mid)
  53.         res |= query(lson, a, b);
  54.     if(b > mid)
  55.         res |= query(rson, a, b);
  56.     return res;
  57. }
  58. int main(){
  59.     int n, m, q;
  60.     scanf("%d %d %d", &n, &m, &q);
  61.     build(root);
  62.     while(q--){
  63.         char c;
  64.         int x, y;
  65.         scanf("\n%c %d %d", &c, &x, &y);
  66.         if(x > y) swap(x, y);
  67.         if(c == 'C'){
  68.             int z;
  69.             scanf(" %d", &z);
  70.             update(root, x, y, z);
  71.         }
  72.         else if(c == 'P'){
  73.             int res = query(root, x, y);
  74.             int ans = 0;
  75.             while(res > 0){
  76.                 ans += res & 1;
  77.                 res >>= 1;
  78.             }
  79.             printf("%d", ans);
  80.             if(q > 0)
  81.                 printf("\n");
  82.         }
  83.         else printf("Error!\n");
  84.     }
  85.     return 0;
  86. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注