赛时过程
ACM赛制。
T1题水贪心，送分题切了过就不说了。
T2一看什么鬼，乱写了个欧拉回路WA了就爬了。
T3明显树状数组。看了一下打了会儿草稿发现异或运算可以消掉很多数，统计一下每个数在所有子序列中出现次数奇偶性，两个数树状数组乱搞就行。过了。
开T4，2h30min的比赛还剩一个多小时，一看觉得是道神题没去管滚回去看T2，舒舒服服地WA了几次回来看T4，瞟到 $n\le 16$ 的数据范围赶紧状压开始码码码，然后在比赛还剩二十分钟时惊险通过。
赛后呢，老板把T2题面抄错了…………全场无人AC……
赛后题解：
说一下C题吧。
何老板给你一个长度为n的整数数列a，数列中每个数字都是32位非负整数。
何老板会多次进行如下两种操作：
1.修改数列中某个数的值
2.询问某个区间内所有子区间的异或和的异或和。
$n\le 2\times 10^5$
子区间的异或和的异或和？？？smg
上次的：”中位数们的中位数“也是这种，老板最喜欢玩这种毒瘤了QwQ
既然是异或，统计一下每个数字在最终的异或和中出现的奇偶性就行。
对于区间 $[l,r]$ 的 $a_i$，它会被异或 $(i-l+1)\times (r-i+1)$ 次。这个次数为奇数我们才考虑这个数。
如果这个次数是奇数，那么 $i-l+1+r-i+1=r+l+2$ 也是奇数。所以 $r-l$ 也是奇数。
然后用两个树状数组维护 $\sum\limits^{2\times i-1\le n}_{i=1}a_{2\times i-1}$ 和 $\sum\limits^{2\times i\le n}_{i=1}a_{2\times i}$ 的和即可。
$Code:$
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
| #include <cstdio>
int a[200005], n, len;
struct BIT {
int c[100005];
inline void update(const int x, const int k, const int d) {
int t(d ^ a[x]);
for (int i(k); i <= len; i += (i & ~i + 1)) c[i] ^= t;
a[x] = d;
}
inline int query(const int x) {
int sum(0);
for (int i(x); i; i -= (i & ~i + 1)) sum ^= c[i];
return sum;
}
} q1, q2;
int main() {
int q;
scanf("%d%d", &n, &q);
len = n + 1 >> 1;
for (int i(1); i <= n; ++ i) {
int x;
scanf("%d", &x);
if (i & 1) q1.update(i, i + 1 >> 1, x);
else q2.update(i, i >> 1, x);
}
while (q --) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
if (l & 1) q1.update(l, l + 1 >> 1, r);
else q2.update(l, l >> 1, r);
}
else {
if (r - l & 1) {puts("0"); continue;}
printf("%d\n", l & 1 ? q1.query(r + 1 >> 1) ^ q1.query(l - 1 >> 1) :
q2.query(r >> 1) ^ q2.query(l - 2 >> 1));
}
}
}
|