首页 > 代码库 > FZU2105 线段树 （按位操作）
FZU2105 线段树 （按位操作）
题目：
Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:
（元素和操作元素 < 16）
Operation 1: AND opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).
Operation 2: OR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).
Operation 3: XOR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).
Operation 4: SUM L R
We want to know the result of A[L]+A[L+1]+...+A[R].
这个题用线段树解决主要在于两个问题：
1、标记表示：如果简单设置3个布尔类型的变量表示3个操作的标记的话，要考虑标记对自己本身的影响和标记间的相互影响，程序会反而复杂，而如果用一个数组记录区间内所有数中每一位（二进制位，共4位）的1的个数，则可以省略and和or两个标记以及sum变量，空间节省不少，程序也简单很多（主要是考虑标记下传的时候方便一些）
说明：
区间的和可以表示为，每一位上1的总个数 * 对应位的权值（1， 2， 4， 8）的和
and操作和or操作都是把当前节点的1的个数置0或者赋为cnt（区间内数的个数），同时又可以通过判断节点的1的个数是否为0或者cnt来表示是否有标记（and或者or，但已不重要，最终只关心1的个数）
2：pushDown()函数的设计：pushDown()函数是区间修改的核心，作用是线段树标记下传过程中维护标记以及节点的它信息，使线段树时时刻刻保持“正确有序”的姿态, 具体参见代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #define mem0(a) memset(a, 0, sizeof(a)) 7 #define lson l, m, rt << 1 8 #define rson m + 1, r, rt << 1 | 1 9 #define lr rt << 1 10 #define rr rt << 1 | 1 11 using namespace std; 12 #define LL __int64 13 struct seg_tree{ 14 int mark;// xor operations‘ mark 15 int cnt[4];//four digits‘ count(used for other operations) 16 }tree[1000010 << 2]; 17 18 void pushUp(int rt) 19 { 20 for(int i = 0; i < 4; i++) { 21 tree[rt].cnt[i] = tree[rt << 1].cnt[i] + tree[rt << 1 | 1].cnt[i]; 22 } 23 } 24 25 void pushDown(int rt, int cnt) 26 { 27 seg_tree &t = tree[rt], &tl = tree[rt << 1], &tr = tree[rt << 1 | 1]; 28 int lc = cnt - (cnt >> 1), rc = cnt >> 1; 29 for(int i = 0; i < 4; i++) { // 按位处理 30 if(t.cnt[i] == cnt || t.cnt[i] == 0) { // 是否全部是0或1 31 tl.mark &= (~(1 << i)); // 左右儿子的标记清0，因为此时以前xor标记不起作用了 32 tr.mark &= (~(1 << i)); 33 tl.cnt[i] = t.cnt[i] > 0 ? lc : 0; // 儿子的1的个数与当前对应 34 tr.cnt[i] = t.cnt[i] > 0 ? rc : 0; 35 t.mark &= (~(1 << i)); // 当前的xor标记清0， 因为子孙的1的个数与当前对应, 当前标记不对当前起作用， 36 //那么也不会对子孙起作用 37 } 38 if(t.mark & (1 << i)) { 39 tl.cnt[i] = lc - tl.cnt[i]; 40 tr.cnt[i] = rc - tr.cnt[i]; 41 tl.mark ^= (1 << i); 42 tr.mark ^= (1 << i); 43 t.mark &= (~(1 << i)); 44 } 45 } 46 } 47 48 void work(int x, int k, int rt, int cnt) 49 { 50 for(int i = 0; i < 4; i++) { 51 if(x & (1 << i)) { 52 if(k == 0) tree[rt].cnt[i] = cnt - tree[rt].cnt[i], tree[rt].mark ^= (1 << i); 53 if(k == 1) tree[rt].cnt[i] = cnt, tree[rt].mark &= (~(1 << i)); 54 } 55 else { 56 if(k == 2) tree[rt].cnt[i] = 0, tree[rt].mark &= (~(1 << i)); 57 } 58 } 59 } 60 61 int calc(int cnt[]) 62 { 63 int sum = 0; 64 for(int i = 0; i < 4; i++) { 65 sum += cnt[i] * (1 << i); 66 } 67 return sum; 68 } 69 70 void build(int l, int r, int rt) 71 { 72 tree[rt].mark = 0; 73 if(l == r) { 74 int x; 75 scanf("%d", &x); 76 for(int i = 0; i < 4; i++) { 77 tree[rt].cnt[i] = ((x & (1 << i)) > 0); 78 } 79 return; 80 } 81 int m = (l + r) >> 1; 82 build(lson); 83 build(rson); 84 pushUp(rt); 85 } 86 int query(int L, int R, int l, int r, int rt) 87 { 88 if(L <= l && r <= R) { 89 return calc(tree[rt].cnt); 90 } 91 int m = (l + r) >> 1, res = 0; 92 pushDown(rt, r - l + 1); 93 if(L <= m) res += query(L, R, lson); 94 if(R > m) res += query(L, R, rson); 95 return res; 96 } 97 98 void update(int L, int R, int x, int k, int l, int r, int rt) 99 {100 if(L <= l && r <= R) {101 work(x, k, rt, r - l + 1);102 return;103 }104 int m = (l + r) >> 1;105 pushDown(rt, r - l + 1);106 if(L <= m) update(L, R, x, k, lson);107 if(R > m) update(L, R, x, k, rson);108 pushUp(rt);109 }110 111 int main(){112 //freopen("input.txt", "r", stdin);113 int T;114 cin >> T;115 while(T--) {116 int n, m;117 cin >> n >> m;118 build(1, n, 1);119 for(int i = 1; i <= m; i++) {120 int a, b;121 char s[10];122 scanf("%s%d%d", s, &a, &b);123 char ch = s[0];124 if(s[0] == ‘S‘) printf("%d\n", query(a + 1, b + 1, 1, n, 1));125 else {126 int c;127 scanf("%d", &c);128 if(ch == ‘X‘) update(b + 1, c + 1, a, 0, 1, n, 1);129 if(ch == ‘O‘) update(b + 1, c + 1, a, 1, 1, n, 1);130 if(ch == ‘A‘) update(b + 1, c + 1, a, 2, 1, n, 1);131 }132 }133 }134 }
FZU2105 线段树 （按位操作）