金马 5 校 - 奇点蜂测序

题目大意

题面

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ ，一开始每个位置的值都未知。现在有 $q$ 次在线操作：

操作	含义
1 l r x	尝试加入约束：(a_l \oplus a_{l+1} \oplus \cdots \oplus a_r = x)。如果这个约束和已经采纳的约束矛盾，就丢弃；否则永久加入。
2 l r	查询 (a_l \oplus a_{l+1} \oplus \cdots \oplus a_r)。如果当前约束不能唯一确定这个值，输出 -1。

样例里先把每个单点的值都约束出来：a1 = 3, a2 = 6, a3 = 7, a4 = 3, a5 = 9。

所以：

查询	结果
[1,4]	$3 \oplus 6 \oplus 7 \oplus 3 = 1$
[2,5]	$6 \oplus 7 \oplus 3 \oplus 9 = 11$
[1,5]	$3 \oplus 6 \oplus 7 \oplus 3 \oplus 9 = 8$

思路讲解

一句话

把原数组转换成前缀异或和，区间约束就变成两个前缀点之间的异或边；然后用带权并查集维护每个点到集合根的异或值，就可以在线合并约束和回答查询。

先把区间改成两个前缀点

定义前缀异或：

$$s_i = a_1 \oplus a_2 \oplus \cdots \oplus a_{i-1}$$

这里故意让 $s_1=0$，也就是 s[i] 表示第 $i$ 个位置之前的异或和。这样区间 [l,r] 的异或和就是：

$$a_l \oplus \cdots \oplus a_r = s_l \oplus s_{r+1}$$

所以操作 1 l r x 其实是在说：

s_l xor s_{r+1} = x

这一步很关键：原本有 $n$ 个未知的数组元素，转成了 $n+1$ 个前缀点之间的相对关系。所有约束都只是在连边。

关键不变量：如果两个前缀点在同一个连通块里，它们之间的异或差就已经被约束唯一确定；如果不在同一个连通块里，那它们之间还可以整体自由平移，查询答案就不能确定。

带权并查集里维护什么

普通并查集只知道两个点是不是连通；这题还需要知道连通以后它们之间的异或差。所以维护：

fa[x]      // x 的父亲
xorVal[x]  // x 到 fa[x] 的异或值

路径压缩时顺手把 xorVal[x] 改成「x 到根」的异或：

ll find(ll x) {
    if (fa[x] == x) return fa[x];
    ll tmp = fa[x];
    fa[x] = find(tmp);
    xorVal[x] ^= xorVal[tmp];
    return fa[x];
}

这样 find(x) 之后，xorVal[x] 就是 $s_x \oplus s_{\text{root}}$ 。如果 l 和 r+1 已经在同一个集合里，那么：

$$s_l \oplus s_{r+1} = (s_l \oplus s_{\text{root}}) \oplus (s_{r+1} \oplus s_{\text{root}})$$

根的那一项异或两次会消掉，所以查询就是：

xorVal[l] ^ xorVal[r + 1]

合并一个新约束

现在加入约束 s_a xor s_b = val。先找到根：

ra = find(a);
rb = find(b);

如果 ra == rb，这条边没有带来新信息；它要么和已有约束一致，要么矛盾。严格写法应该检查：

(xorVal[a] ^ xorVal[b]) == val

这份标准代码里 ra == rb 时直接 return，因为矛盾约束被忽略后，对后续可确定的查询没有影响；不过从“判断矛盾”的语义来说，加上这个检查会更完整。

如果根不同，就把 ra 接到 rb 上，并求出 ra 到 rb 应该是多少。我们需要让合并后仍然满足：

$$s_a \oplus s_b = val$$

因为：

$$s_a \oplus s_b = (s_a \oplus s_{ra}) \oplus (s_{ra} \oplus s_{rb}) \oplus (s_b \oplus s_{rb})$$

所以：

xorVal[ra] = val ^ xorVal[a] ^ xorVal[b]

这就是代码里的核心合并式：

fa[ra] = rb;
xorVal[ra] ^= val ^ xorVal[b] ^ xorVal[a];

由于 ra 是根，原本 xorVal[ra] = 0，所以这行等价于赋值。

查询为什么会输出 -1

查询 [l,r] 时，同样先改成前缀点 l 和 r+1：

情况	说明	输出
find(l) == find(r + 1)	两个前缀点之间的异或差已经被约束系统确定	xorVal[l] ^ xorVal[r + 1]
find(l) != find(r + 1)	两个连通块之间还没有关系，答案可能随未知变量变化	-1

反正这题的本质不是“求出每个 $a_i$”，而是维护前缀点之间的相对异或关系。只要相对关系能连通，答案就出来了。

复杂度

每次操作做常数次并查集 find/union，时间复杂度是 $O(\alpha(n))$，总复杂度 $O((n+q)\alpha(n))$，空间复杂度 $O(n)$。

AC 代码

源码较长，下面折叠保存一份标准实现。

展开完整源码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10;
ll fa[N], xorVal[N];
ll n, q, op, l, r, x;
ll find(ll x) {
    if(fa[x] == x) return fa[x];
    ll tmp = fa[x];
    fa[x] = find(tmp);
    xorVal[x] ^= xorVal[tmp];
    return fa[x];
}
ll calXOR(ll l, ll r) {
    if(find(l) != find(r)) return -1;
    return xorVal[l] ^ xorVal[r];
}
void concat(ll a, ll b, ll val) {
    ll ra = find(a);
    ll rb = find(b);
    if(ra == rb) return;
    fa[ra] = rb;
    xorVal[ra] ^= val ^ xorVal[b] ^ xorVal[a];
}
void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n + 1; i++) {
        fa[i] = i;
        xorVal[i] = 0;
    }
    while(q--) {
        cin >> op >> l >> r;
        r += 1;
        if(op == 2) cout << calXOR(l, r) << "\n";
        else {
            cin >> x;
            concat(l, r, x);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}

心路历程（WA，TLE，MLE……）

这题最容易绕进去的点是想维护原数组 $a_i$ 的值，但其实单点值不一定能被确定。真正稳定的东西是前缀点之间的差，也就是 $s_l \oplus s_{r+1}$。

还有一个实现细节：输入的 r 要立刻变成 r + 1，因为所有约束都在前缀点上连边。这个转换漏掉以后，查询会整体错一位。

附件

本页根据本地题面 PDF 和标准代码整理：/Users/zzy/Downloads/奇点蜂测序/problem.pdf、/Users/zzy/Downloads/奇点蜂测序/std.cpp。