P6225异或橙子

题意

一个长度为 $n$ 的序列，每个数有一个初始值 $a_i$，维护以下 $q$ 个操作：

  • 单点修改
  • 给定区间 $[l, r]$ 求其所有子区间的异或和

对于所有数据，$0\le a_i\le 10^9,1\le n,q\le 2\times 10^5$

分析

01-枚举

对于每一次询问，暴力枚举其所有子区间，时间复杂度 $O(qn^2)$ ，无法接受，故尝试分析特殊性质。

02-特殊性质

考虑到运算符为异或，而异或运算有以下性质：

  • x ^ x = 0
  • x ^ 0 = x

得到启发：

如果所有子区间中一个数出现了偶数次，那么这个数不影响答案。
反之，若出现奇数次，则计算答案。

03-正解

考虑一个长度为偶数区间 $[a_1,\ldots ,a_4]$ 的所有子区间，统计每一个数的操作次数：

区间长度 $a_1$ $a_4$ $a_3$ $a_4$
1 1 1 1 1
2 1 2 2 1
3 1 2 2 1
4 1 1 1 1
总计 4 6 6 4
  • 发现每一个数都出现了偶数次，答案为 $0$ 。
  • 显而易见对于所有偶数长度的区间都成立。

考虑一个长度为奇数区间 $[a_1,\ldots ,a_5]$ 的所有子区间，统计每一个数的操作次数：

区间长度 $a_1$ $a_2$ $a_3$ $a_4$ $a_5$
1 1 1 1 1 1
2 1 2 2 2 1
3 1 2 3 2 1
4 1 2 2 2 1
5 1 1 1 1 1
总计 5 8 9 8 5
& $1$ 1 0 1 0 1
  • 发现对于一个长度为奇数的区间，只需要考虑所有奇数项的异或和即可。
  • 显而易见，对于所有长度为奇数的区间都成立。

综上，只需要一个维护区间异或和的数据结构就可以解决本题。

04-实现

考虑用两个树桩数组解决问题：

  • 第一个：维护前缀异或和（即区间异或和）
  • 第二个：维护奇数项前缀异或和

当然，还有另一种方式;

  • 第一个：维护偶数项前缀异或和
  • 第二个：维护奇数项前缀异或和

它们的原理相同，难度相似，我选用第一种（只写了这个）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n, q;
int a[N];

struct bitree { //写的真好
    int c[N], res;
    inline int lb(int x) {
        return x & (-x);
    }
    inline void add(int x, int v) {
        for (; x <= n; x += lb(x))
            c[x] ^= v;
    }
    inline int find(int x) {
        for (res = 0; x; x -= lb(x))
            res ^= c[x];

        return res;
    }
    inline int find(int x, int y) {
        return find(y) ^ find(x - 1);
    }
} tr, tr1;

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i], tr.add(i, a[i]);

        if (i & 1) tr1.add(i, a[i]);
    }

    for (int op, x, y; q--; ) {
        cin >> op >> x >> y;

        if (op == 1) {
            tr.add(x, a[x] ^ y);
						// a[x] : 消除原来的影响
						// y : 更改后的值
            if (x & 1) tr1.add(x, a[x] ^ y);

            a[x] = y; 
            //记录更改后的值

        } else {
            if ((y - x + 1) & 1) {
                int res = tr1.find(x, y);

                if (!(x & 1)) res ^= tr.find(x, y);
									//   1 1 1 1 1
									// ^ 1 0 1 0 1
									//-------------
									//   0 1 0 1 0
									
                cout << res << endl;

            } else cout << 0 << endl;
        }
    }


    return 0;
}

QAQ

Written with StackEdit中文版.