POJ 2777 Count Color——区间更新的线段树+状态压缩

POJ 2777 Count Color——区间更新的线段树+状态压缩

题意：用数字表示颜色，一开始n个物品的颜色全部为1，可以进行操作x y z，把区间【x，y】的颜色全部变为z，求给定区间内有多少种不同的颜色

思路：首先想到套用区间更新的线段树模板，但是因为线段树维护的是颜色的种数，因此不能单纯的求和，这就用到了位运算，用数字来保存状态，用位运算进行操作，具体参考代码

PS：注意输入的【x，y】可能出现x > y的情况， 注意交换

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;int N, T, O, segTree[maxn<<2], lazy[maxn<<2];void pushup(int root) { segTree[root] = segTree[root<<1] | segTree[root<<1|1];}void pushdown(int root) { if (lazy[root]) { lazy[root<<1] = lazy[root]; lazy[root<<1|1] = lazy[root]; segTree[root<<1] = 1<<(lazy[root] - 1); segTree[root<<1|1] = 1<<(lazy[root] - 1); lazy[root] = 0; }}void build(int L, int R, int root) { if (L == R) { segTree[root] = 1; return; } int mid = (L + R)>>1; build(L, mid, root<<1); build(mid + 1, R, root<<1|1); pushup(root);}void update_interval(int L, int R, int root, int uL, int uR, int val) { if (uL <= L && R <= uR) { segTree[root] = 1<<(val - 1); lazy[root] = val; return; } int mid = (L + R)>>1; pushdown(root); if (uL <= mid) { update_interval(L, mid, root<<1, uL, uR, val); } if (uR > mid) { update_interval(mid + 1, R, root<<1|1, uL, uR, val); } pushup(root);}int query(int L, int R, int root, int qL, int qR) { if (qL <= L && R <= qR) { return segTree[root]; } int mid = (L + R)>>1; pushdown(root); int ans = 0; if (qL <= mid) { ans |= query(L, mid, root<<1, qL, qR); } if (qR > mid) { ans |= query(mid + 1, R, root<<1|1, qL, qR); } return ans;}int main(){ while (scanf("%d %d %d", &N, &T, &O) == 3) { memset(segTree, 0, sizeof(segTree)); memset(lazy, 0, sizeof(lazy)); build(1, N, 1); while (O--) { char c; cin >> c; if (c == 'C') { int x, y, z; scanf("%d %d %d", &x, &y, &z); if (x > y) swap(x, y); update_interval(1, N, 1, x, y, z); } else if (c == 'P') { int x, y; scanf("%d %d", &x, &y); if (x > y) swap(x, y); int ans = query(1, N, 1, x, y), cnt = 0; for (int i = 0; i < T; i++) { if ((ans>>i) & 1) { cnt++; } } printf("%d\n", cnt); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。