POJ 2777 - Count Color

http://poj.org/problem?id=2777

概要

\(L\) 個の板が一直線に並んでおり、これらに関して \(O\) 個の以下のような2種類の操作を行う。

  1. "C A B T". A 番目から B 番目までの板を色 C で塗る
  2. "P A B". A 番目から B 番目までの板に何種類の色が存在するか出力する

制約

解法

セグメント木を用いてどちらの操作も \(O(\log L)\) で行えるようにする。 色は高々30種類しかないので、各区間に存在する色はビットフラグで管理することができる。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 static const int MAXL = 100000;
 6 
 7 struct SegmentTree
 8 {
 9   unsigned tree[4*MAXL];
10   int L;
11   SegmentTree(int l) : L(l)
12   {
13     fill_n(tree, 4*MAXL, 0);
14     tree[0] = 1<<0;
15   }
16 
17   void paint(int from, int to, int c)
18   {
19     paint(from, to, c, 0, 0, L);
20   }
21   void paint(int from, int to, int c, int i, int left, int right)
22   {
23     if (right <= from || to <= left) {
24       // does not intersect
25     } else if (from <= left && right <= to) {
26       // included
27       tree[i] = 1<<c;
28     } else {
29       if (__builtin_popcount(tree[i]) == 1) {
30         tree[2*i+1] = tree[2*i+2] = tree[i];
31       }
32       const int m = (left+right)/2;
33       paint(from, to, c, 2*i+1, left, m);
34       paint(from, to, c, 2*i+2, m, right);
35       tree[i] = tree[2*i+1] | tree[2*i+2];
36     }
37   }
38 
39   int query(int from, int to) const
40   {
41     return __builtin_popcount(query(from, to, 0, 0, L));
42   }
43   unsigned query(int from, int to, int i, int left, int right) const
44   {
45     if (right <= from || to <= left) {
46       // does not intersect
47       return 0;
48     } else if (from <= left && right <= to) {
49       // included
50       return tree[i];
51     } else {
52       if (__builtin_popcount(tree[i]) == 1) {
53         return tree[i];
54       } else {
55         const int m = (left+right)/2;
56         return query(from, to, 2*i+1, left, m) | query(from, to, 2*i+2, m, right);
57       }
58     }
59   }
60 };
61 
62 int main()
63 {
64   int L, T, O;
65   scanf("%d %d %d", &L, &T, &O);
66   static SegmentTree segtree(L);
67   while (O-- > 0) {
68     char o[4];
69     int A, B;
70     scanf("%s %d %d", o, &A, &B);
71     if (A > B) {
72       swap(A, B);
73     }
74     --A;
75     if (*o == 'C') {
76       int C;
77       scanf("%d", &C);
78       --C;
79       segtree.paint(A, B, C);
80     } else {
81       printf("%d\n", segtree.query(A, B));
82     }
83   }
84   return 0;
85 }
poj/2777.cc