P6225 异或橙子
题意简述
给定一个序列，需要维护一下两个操作：
- 单点赋值
- 求给定区间的所有子区间的异或和的异或和。
题解
可以观察样例： 
发现在求答案的时候有些数是被抵消的，因为一个数异或偶数次后就变为 $0$ 了。
所以我们可以观察到只有当询问区间长度是奇数的时候，答案不为 $0$ 且答案是隔一个异或一个。
证明：
令区间的第一个数为 $b_1$，第二个数为 $b_2$，也就是说 $a_l = b_1$，$a_{l + 1} = b_2$，以此类推。
再令区间长度为 $x$。
那么 $b_i$ 计算的个数为 $i \times (x - i + 1)$。
不难发现如果 $x$ 是偶数，那么每个数出现的次数都必定是偶数，而由于异或的性质，所以答案必定是 $0$。
如果 $x$ 为奇数，那么可以发现只有当 $i$ 是奇数的时候 $b_i$ 计算的次数是奇数，也只有这些数的答案需要被异或。
那么我们可以维护两个树状数组，一个维护奇数位上的数的单点赋值和区间异或，一个维护偶数位上的。
这样的话直接按照上面的理论就可以了，具体实现可以看代码。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
*/
int n, m;
int a[1000005][5];
int lb(int x) {return x & (-x);}
void add(int x, int y, int t) {
// cout << a[2][t] << " " << y << " " << t << "\n";
for (; x <= n; x += lb(x)) a[x][t] ^= y;
}
int query(int x, int t) {
int sum = 0;
for (; x >= 1; x -= lb(x)) sum ^= a[x][t];
return sum;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
int x; cin >> x;
add(i, x, i % 2);
// cout << (i + 1) / 2 << " " << x << " " << i % 2 << "\n";
}
// cout << query(2, 1) << "\n";
while (m --) {
int op, x, y; cin >> op >> x >> y;
if (op == 1) {
int old = query(x, x % 2) ^ query(x - 1, x % 2);
add(x, old, x % 2);
add(x, y, x % 2);
} else {
// cout << (x + 1) / 2 << " " << (y + 1) / 2 << " " << query(2, 1) << " !\n";
if ((y - x + 1) % 2 == 1) {
cout << (query(x - 1, x % 2) ^ query(y, x % 2)) << "\n";
} else {
// cout << (query(x - 1, (x + 1) % 2) ^ query(y, (x + 1) % 2)) << "\n";
cout << 0 << "\n";
}
}
}
return 0;
}
评论 (0)