首页 > 代码库 > POJ 2777 线段树
POJ 2777 线段树
链接：
http://poj.org/problem?id=2777
题意：
有L个气球，开始颜色为1，每次给l，r之间的气球染色x，然后询问l，r区间有多少种不同的颜色
题解：
因为颜色最多有30种，所以对这30中颜色状态压缩一下，放在线段树里面，这样就容易更新了
最后只要计算一下query返回值得数有多少个1就行了
代码：
31 int L, T, O; 32 int Tree[MAXN << 2]; 33 int Lazy[MAXN << 2]; 34 35 int BitCount(int n) { 36 int c = 0; 37 for (c = 0; n; ++c) n &= (n - 1); 38 return c; 39 } 40 41 void pushup(int rt) { 42 Tree[rt] = Tree[rt << 1] | Tree[rt << 1 | 1]; 43 } 44 45 void pushdown(int rt) { 46 if (Lazy[rt]) { 47 Tree[rt << 1] = Lazy[rt]; 48 Tree[rt << 1 | 1] = Lazy[rt]; 49 Lazy[rt << 1] = Lazy[rt]; 50 Lazy[rt << 1 | 1] = Lazy[rt]; 51 Lazy[rt] = 0; 52 } 53 } 54 55 void build(int l,int r,int rt) { 56 if (l == r) { 57 Tree[rt] = 1; 58 return; 59 } 60 int m = (l + r) >> 1; 61 build(lson); 62 build(rson); 63 pushup(rt); 64 } 65 66 void update(int L, int R, int x, int l, int r, int rt) { 67 if (L <= l && r <= R) { 68 Tree[rt] = (1 << x); 69 Lazy[rt] = (1 << x); 70 return; 71 } 72 pushdown(rt); 73 int m = (l + r) >> 1; 74 if (L <= m) update(L, R, x, lson); 75 if (R > m) update(L, R, x, rson); 76 pushup(rt); 77 } 78 79 int query(int L, int R, int l, int r, int rt) { 80 if (L <= l && r <= R) return Tree[rt]; 81 pushdown(rt); 82 int m = (l + r) >> 1; 83 int ret = 0; 84 if (L <= m) ret |= query(L, R, lson); 85 if (R > m) ret |= query(L, R, rson); 86 return ret; 87 } 88 89 int main() { 90 ios::sync_with_stdio(false), cin.tie(0); 91 cin >> L >> T >> O; 92 build(1, L, 1); 93 while(O--) { 94 char c; 95 cin >> c; 96 if (c == ‘C‘) { 97 int a, b, x; 98 cin >> a >> b >> x; 99 if (a > b) swap(a, b);100 update(a, b, x - 1, 1, L, 1);101 }102 else {103 int a, b;104 cin >> a >> b;105 if (a > b) swap(a, b);106 cout << BitCount(query(a, b, 1, L, 1)) << endl;107 }108 }109 return 0;110 }
POJ 2777 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。