PKU 2777 Count Color
板があって、ある区間に色を塗るクエリとある区間の色の種類を数えるクエリが来るので高速に処理しろという問題です。
どうでみてもsegment treeだが区間の左右が逆なこともあるよとか言う制約読んでいなかった...
#include <cstdio> #include <algorithm> using namespace std; #define rep(i, n) for(int i = 0; i < (int)n; ++i) #define SZ (1 << 18) int len, t, o, sz; struct NODE{ int c, lazy; NODE(){ c = lazy = 0; } }; struct segtree{ NODE dat[SZ * 2]; inline void lazy_eval(int k){ if(k < SZ - 1 && dat[k].lazy){ dat[k].c = dat[k].lazy; dat[k * 2 + 1].lazy = dat[k].lazy; dat[k * 2 + 2].lazy = dat[k].lazy; } dat[k].lazy = 0; } inline void up_node(int k){ dat[k].c = dat[k * 2 + 1].c | dat[k * 2 + 2].c; } inline void paint(int a, int b, int c, int k = 0, int l = 0, int r = sz){ lazy_eval(k); if(r <= a || b <= l) return ; if(a <= l && r <= b){ dat[k].lazy = (1 << (c - 1)); lazy_eval(k); return ; } paint(a, b, c, k * 2 + 1, l, (l + r) / 2); paint(a, b, c, k * 2 + 2, (l + r) / 2, r); up_node(k); } int cnt(int a, int b, int k = 0, int l = 0, int r = sz){ lazy_eval(k); if(r <= a || b <= l) return 0; if(a <= l && r <= b) return dat[k].c; int lch = cnt(a, b, k * 2 + 1, l, (l + r) / 2); int rch = cnt(a, b, k * 2 + 2, (l + r) / 2, r); up_node(k); return lch | rch; } }seg; int main(){ scanf("%d %d %d", &len, &t, &o); sz = 1; while(sz < len) sz *= 2; seg.paint(0, len, 1); while(o--){ char q[3]; scanf("%s", q); if(q[0] == 'C'){ int a, b, c; scanf("%d %d %d", &a, &b, &c); if(a > b) swap(a, b); seg.paint(a - 1, b, c); }else{ int a, b; scanf("%d %d", &a, &b); if(a > b) swap(a, b); printf("%d\n", __builtin_popcount(seg.cnt(a - 1, b))); } } return 0; }
遅延評価慣れてきました。