XOR on segment(线段树区间异或更新)

本题大意：给定n个数字和m个操作，操作共有两种，第一种是求解区间l到r上元素的和，第二种是将区间l到r的元素都异或一个x，作为某个位置的新值。

很容易想到线段树维护区间和，但是我们发现，在区间更新的时候，并没有办法更新，因为我们并不能通过一个区间的和还有我们要异或的值得到这个区间新的异或和，那么我们考虑其他方法。

下面讲述的这个方法，对于值域不大于1 << 20的数据，我们选择用20个数组保存某一个区间k中第 i 位的1的个数，为什么要这么搞呢？

对于第i位，如果区间k的第 i 位原本有s[ i ][ k ]个1，那么对这个区间所有数字都异或一个数字x，我们只需要判断 x 的每一位，如果存在第 i 位为1，那么s[ i ][ k ] = 区间长度 - s[ i ][ k ]。如果第 i 位为0，那么我们忽略这一位。

why ？？？？

0 xor 1 = 1.... 0 xor 0 = 0 也就是说o异或任何值等于任何值。

1 xor 0 = 1.......1 xor 1 = 0 也就是说与1异或之后值变为相反数。所以区间内1的个数就变为了区间中零的个数。

这样我们就可以轻松统计某个区间某一位上有多少个1。query操作相信应该都是明了的。

那么懒惰标记如何处理呢？？

当然是用一个数组lazy_lable记录区间k应该往下推的值，如果该值还未下推又来了另一个值需要改变，那么就将这两个值异或起来，多者不限，也就是说只需要一个一维数组来记录每个区间的lazy值就行了。

ok相信大家都懂了，本来讲之前本人还不怎么懂。。。。。结果讲完就懂了。。。舒服

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define mid ((l + r) >> 1)
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 
 9 const int maxn = 100000 + 5;
10 
11 ll segment_tree[22][maxn << 2], lazy_lable[maxn << 2];
12 
13 int n, m, x;
14 
15 void push_up(int k) {
16     for(int i = 0; i < 22; i ++) {
17         segment_tree[i][k] = segment_tree[i][k << 1] + segment_tree[i][k << 1 | 1];
18     }
19 }
20 
21 void push_down(int k, int son) {
22     if(lazy_lable[k]) {
23         lazy_lable[k << 1] ^= lazy_lable[k];
24         lazy_lable[k << 1 | 1] ^= lazy_lable[k];
25         for(int i = 0; i < 22; i ++) {
26             if((lazy_lable[k] >> i) & 1) {
27                 segment_tree[i][k << 1] = son - (son >> 1) - segment_tree[i][k << 1];
28                 segment_tree[i][k << 1 | 1] = (son >> 1) - segment_tree[i][k << 1 | 1];
29             }
30         }
31         lazy_lable[k] = 0;
32     }
33 }
34 
35 void build(int l, int r, int k) {
36     if(l == r) {
37         scanf("%d", &x);
38         for(int i = 0; i < 22; i ++) {
39             if((x >> i) & 1)
40                 segment_tree[i][k] = 1;
41         }
42         return;
43     }
44     build(l, mid, k << 1);
45     build(mid + 1, r, k << 1 | 1);
46     push_up(k);
47 }
48 
49 void update(int L, int R, int x, int l, int r, int k) {
50     if(L <= l && R >= r) {
51         lazy_lable[k] ^= x;
52         for(int i = 0; i < 22; i ++) {
53             if((x >> i) & 1) {
54                 segment_tree[i][k] = r - l + 1 - segment_tree[i][k];
55             }
56         }
57         return;
58     }
59     push_down(k, r - l + 1);
60     if(L <= mid) update(L, R, x, l, mid, k << 1);
61     if(R > mid) update(L, R, x, mid + 1, r, k << 1 | 1);
62     push_up(k);
63 }
64 
65 ll query(int L, int R, int l, int r, int k) {
66     if(L <= l && R >= r) {
67         ll cnt = 0;
68         for(int i = 0; i < 22; i ++) {
69             cnt += segment_tree[i][k] << i;
70         }
71         return cnt;
72     }
73     push_down(k, r - l + 1);
74     ll ans = 0;
75     if(L <= mid) ans += query(L, R, l, mid, k << 1);
76     if(R > mid) ans += query(L, R, mid + 1, r, k << 1 | 1);
77     return ans;
78 }
79 
80 int main() {
81     int op, l, r, x;
82     scanf("%d", &n);
83     build(1, n, 1);
84     scanf("%d", &m);
85     while(m --) {
86         scanf("%d", &op);
87         if(op == 1) {
88             scanf("%d %d", &l, &r);
89             printf("%lld\n", query(l, r, 1, n, 1));
90         } else {
91             scanf("%d %d %d", &l, &r, &x);
92             update(l, r, x, 1, n, 1);
93         }
94     }
95     return 0;
96 }

XOR on segment(线段树区间异或更新)

推荐阅读