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
", 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 }

View Code

FZU2105 线段树 （按位操作）

FZU2105 线段树（按位操作）