【题解（异或拆位 trick）】GDKOI2016 魔卡少女 + CF242E XOR on Segment
GDKOI2016 魔卡少女 + CF242E XOR on Segment
是两道题的题解
这两道题都用了异或拆位的套路
GDKOI2016 魔卡少女
题面
给定一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)，\(m\) 次操作，操作内容如下
- 给定 \(p, x\)，将 \(a_p\) 修改为 \(x\)。
- 给定 \(l, r\)，询问区间 \([l, r]\) 的魔法效果。
其中，魔法效果的定义为：\([l, r]\) 中所有 连续子序列的异或和 之和。
\(n,m\le 10^5~,~0\le a_i,x\le10^3\)。
没读懂题？查看原题面。
题解
注意到值域很小，\(0\le a_i\le 1000\)，对应的二进制最多有 \(10\) 位（\(2^{10}=1024>1000\)），考虑对所有 \(10\) 个二进制位维护一颗线段树。
对于修改，由于异或每一位的运算独立，所以对于 \(x\) 二进制下的所有位单独修改即可。
对于询问，我们考虑从所有 \(10\) 个二进制位，最终答案是所有二进制位的贡献之和（这是因为位与位之间独立，即不进位）。
对于第 \(i\) 个二进制位，贡献为 \(2^i\times num\)，其中 \(num\) 表示 \([l, r]\) 中所有异或和 \(=1\) 的子区间的数量。
- 理解：仅考虑第 \(i\) 位，所有位置上的数 \(\in \{0, 1\}\)，所以所有子区间异或和 \(\in\{0, 1\}\)。联系题目所求，可以知道对于异或和为 \(1\) 的子区间，贡献为 \(1\times 2^i\)（二进制下第 \(i\) 位实际为 \(2^i\)）；异或和为 \(0\) 的没有贡献。所以第 \(i\) 位的贡献位 \(2^i\times num\)。
考虑怎么在线段树上维护子区间异或和为 \(1\) 的数量，我们可以维护这些值
-
\(l[0/1]\)：表示连续子序列从左端点(不包含右端点)开始异或和为 \(0/1\) 的子序列数量。
-
\(r[0/1]\)：表示连续子序列从右端点(不包含左点)开始异或和为 \(0/1\) 的子序列数量。
-
\(sum\)：区间异或和。
-
\(num\)：即上文的”子区间异或和为 \(1\) 的数量“。
转移如下
// Node 是线段树上的一个结点对应的结构体
friend Node operator + (Node lhs, Node rhs) { // lhs左区间，rhs右区间
Node res;
res.sum = lhs.sum ^ rhs.sum;
res.l[0] = lhs.l[0] + rhs.l[lhs.sum]; // "+ rhs.l[lhs.sum]"解释：如果lhs异或和为1，那么rhs也为1，异或起来才是0
res.l[1] = lhs.l[1] + rhs.l[lhs.sum ^ 1]; // 同上，反之亦然
res.r[0] = rhs.r[0] + lhs.r[rhs.sum]; // 同理
res.r[1] = rhs.r[1] + lhs.r[rhs.sum ^ 1]; // 同理
res.ans = lhs.ans + rhs.ans + 1ll * lhs.r[0] * rhs.l[1] + 1ll * lhs.r[1] * rhs.l[0]; // "+ 1ll * lhs.r[0] * rhs.l[1]"解释：lhs右边异或和为0，rhs左边异或和为1，总异或和为1
return res;
}
然后就做完了，时间和空间复杂度都是 \(O(n\log{n}\log{a_i})\)。
总结：异或拆位套路
- 异或位与位之间独立，所以可以拆开处理。
- 值域不能太大，否则线段树开不下，时间也不太能过。
- 考虑每一位贡献的时候，记得 \(\times 2^i\)。
代码
点击查看代码
#include
using namespace std;
using i64 = long long;
const int N = 1E5 + 5;
const i64 P = 1E8 + 7;
int n, m;
struct Node {
int l[2], r[2];
i64 sum, num; // sum是异或和，num是所有连续子区间异或为1的数量
Node() { l[0] = l[1] = r[0] = r[1] = sum = num = 0; }
Node(int x) {
l[1] = r[1] = sum = num = x;
l[0] = r[0] = x ^ 1;
}
friend Node operator + (Node lhs, Node rhs) {
Node res;
res.sum = lhs.sum ^ rhs.sum;
res.l[0] = lhs.l[0] + rhs.l[lhs.sum];
res.l[1] = lhs.l[1] + rhs.l[lhs.sum ^ 1];
res.r[0] = rhs.r[0] + lhs.r[rhs.sum];
res.r[1] = rhs.r[1] + lhs.r[rhs.sum ^ 1];
res.num = lhs.num + rhs.num + 1ll * lhs.r[0] * rhs.l[1] + 1ll * lhs.r[1] * rhs.l[0];
return res;
}
};
struct SegementTree {
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) >> 1)
Node t[N * 4];
void update(int rt, int l, int r, int x, int val) {
if(l == r) {
t[rt] = Node(val);
return;
}
if(x <= mid) {
update(lson, l, mid, x, val);
} else {
update(rson, mid + 1, r, x, val);
}
t[rt] = t[lson] + t[rson];
}
Node query(int rt, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return t[rt];
}
Node res;
if(L <= mid) {
res = res + query(lson, l, mid, L, R);
}
if(R > mid) {
res = res + query(rson, mid + 1, r, L, R);
}
return res;
}
#undef mid
} seg[10];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; ++i) {
int x;
cin >> x;
for(int j = 0; j < 10; ++j) {
seg[j].update(1, 1, n, i, (x >> j) & 1);
}
}
cin >> m;
while(m--) {
char opt[10];
cin >> opt;
if(opt[0] == 'Q') {
int l, r;
cin >> l >> r;
i64 num = 0;
for(int j = 0; j < 10 ; ++j) {
Node now = seg[j].query(1, 1, n, l, r);
num += now.num << j;
}
cout << num % P << "\n";
} else {
int x, val;
cin >> x >> val;
for(int j = 0; j < 10; ++j) {
seg[j].update(1, 1, n, x, (val >> j) & 1);
}
}
}
return 0;
}
CF242E XOR on Segment
其实比上一题还简单一些，可以当作练习。
题面
给定长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)。有 \(m\) 次操作，操作内容如下：
- 给定 \(l, r\)，求 \(\sum\limits_{i=l}^ra_i\)。
- 给定 \(l, r, x\)，将 \(a_l\) ~ \(a_r\) 异或上 \(x\)。
\(n\le 10^5~,~m\le 5\times10^4~,~0\le a_i,x\le 10^6\)。
题解
由于修改操作是区间异或，我们联想到了刚才的拆位。\(\log_2{a_i}\le 20\)，需要拆成 \(20\) 位，感觉可以接受。
对于修改，相当于每一位区间异或 \(0/1\)，考虑用线段树维护区间和。
维护这个比上一题简单多了，统计区间内 \(0\) 与 \(1\) 的数量，根据异或值的不同更新这两个值即可。
询问区间和相信大家都会，此处略去。时间和空间复杂度都是 \(O(n\log{n}\log{a_i})\)。
代码
点击查看代码
#include
using namespace std;
using i64 = long long;
const int N = 1E5 + 5;
const int M = 5E4 + 4;
int n, m;
struct SegmentTree {
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) / 2)
i64 sum[N * 4][2], tag[N * 4];
void pushdown(int rt, int l, int r) {
if(tag[rt] != -1) {
tag[lson] = tag[lson] == -1 ? tag[rt] : tag[lson] ^ tag[rt];
tag[rson] = tag[rson] == -1 ? tag[rt] : tag[rson] ^ tag[rt];
// [l, mid] 01 更新
int one, zero;
one = sum[lson][tag[rt] ^ 1];
zero = sum[lson][tag[rt]];
sum[lson][0] = zero;
sum[lson][1] = one;
// [mid + 1, r] 01 更新
one = sum[rson][tag[rt] ^ 1];
zero = sum[rson][tag[rt]];
sum[rson][0] = zero;
sum[rson][1] = one;
// -1 为 tag[rt] 标记空值
tag[rt] = -1;
}
}
void pushup(int rt) {
sum[rt][0] = sum[lson][0] + sum[rson][0];
sum[rt][1] = sum[lson][1] + sum[rson][1];
}
void build(int rt, int l, int r) {
tag[rt] = -1;
sum[rt][0] = r - l + 1; // 一开始全部赋值为 0
if(l == r) {
return;
}
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int L, int R, i64 val) {
if(L <= l && r <= R) {
tag[rt] = tag[rt] == -1 ? val : tag[rt] ^ val;
// [l, r] 01 更新
int one = sum[rt][val ^ 1], zero = sum[rt][val];
sum[rt][0] = zero;
sum[rt][1] = one;
return;
}
pushdown(rt, l, r);
if(L <= mid) {
update(lson, l, mid, L, R, val);
}
if(R > mid) {
update(rson, mid + 1, r, L, R, val);
}
pushup(rt);
}
int query(int rt, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return sum[rt][1];
}
pushdown(rt, l, r);
int res = 0;
if(L <= mid) {
res += query(lson, l, mid, L, R);
}
if(R > mid) {
res += query(rson, mid + 1, r, L, R);
}
return res;
}
#undef mid
} seg[20];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < 20; ++i) {
seg[i].build(1, 1, n); // 初始化所有二进制位上的线段树
}
for(int i = 1; i <= n; ++i) {
int x;
cin >> x;
for(int j = 0; j < 20; ++j) {
seg[j].update(1, 1, n, i, i, (x >> j) & 1);
}
}
cin >> m;
for(int i = 1; i <= m; ++i) {
int opt, l, r;
cin >> opt >> l >> r;
if(opt == 1) {
i64 ans = 0;
for(int j = 0; j < 20; ++j) {
ans += 1ll * (1 << j) * seg[j].query(1, 1, n, l, r);
}
cout << ans << '\n';
} else {
i64 x;
cin >> x;
for(int j = 0; j < 20; ++j) {
seg[j].update(1, 1, n, l, r, (x >> j) & 1);
}
}
}
return 0;
}