通过主席树维护按秩合并的并查集，完全放弃路径压缩以防止空间爆炸，解决强制在线的可持久化维护问题。
OJ: roj
题目 ID: 3133
难度:提高+/省选-
标签:线段树并查集数据结构主席树
创建: 2026-10-09 11:38
更新: 2026-10-09 11:38
形式化题目
给定 last_ans，以得到真实的参数（last_ans 初始值为
1 a b：合并真实参数和 所在的集合。 2 k：回到第（真实参数）次操作之后的状态（初始状态为第 次操作后）。 3 a b：询问真实参数和 是否属于同一集合。如果是，输出 ，否则输出 。并在此时用输出的结果更新 last_ans。
正解
思路
本题要求维护一个可以回退历史版本的并查集。我们使用可持久化线段树（主席树）作为底层数据结构，来维护可持久化数组 fa 和 dep。
其中 fa[x] 记录节点 dep[x]（秩）记录树的深度。
强制在线机制
每次进行操作 1 和操作 3 时，需要将输入的参数 last_ans。操作 2 需要将输入的 last_ans。
last_ans 初始化为 0，只有当且仅当发生操作 3（即查询操作）时，last_ans 会被赋予新查询的答案（0 或 1）。
为何绝对不能使用路径压缩？ 普通的并查集通过路径压缩将均摊复杂度降至非常低。但在可持久化数据结构中，由于可以“退回过去”，攻击者可以构造数据反复查询某个深层节点的祖先，让原本的均摊特性完全失效。在这里“不能路径压缩”有两个维度的致命问题：
- 持久化版路径压缩（新建节点）导致空间爆炸：在查询祖先时，如果把路径上每个节点的
fa均指向根，会导致线段树在单词查询中就需要新建大量版本。实测下最坏构造会导致超过个节点，需要 178MB 内存，直接导致内存越界崩溃（Bus error）。 - 就地路径压缩（不新建节点，直接修改）导致答案错误：若为了省空间直接在原节点上修改
fa，由于多个历史版本共享这些节点，这会彻底破坏旧版本的结构，导致回退操作失效。
因此，只能使用按秩合并（即按深度合并），确保树的深度严格不超过
空间优化设计
使用结构体数组或直接使用 ls/rs/val 三个整型数组维护节点信息。叶子节点需要存储 val 的低 20 位与高 12 位，这样单节点仅占用 12 字节。实测最坏构造输入时需要
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 09:30
# update_at: 2026-10-09 11:24
import sys
# 主席树（可持久化线段树）维护 fa[]：结点 3 个平行 list 存左右儿子与叶子值
# 与 C++ 版同阶：每次 find 跳 O(log n) 次、每次查询 O(log n)，总 O(m log^2 n)
MAX_NODES = 8500000
ls = [0] * MAX_NODES # 左儿子编号
rs = [0] * MAX_NODES # 右儿子编号
val = [0] * MAX_NODES # 叶子值：fa | (dep << 20)
node_cnt = 0
FA_MASK = (1 << 20) - 1
def build(l: int, r: int) -> int:
"""建初始版本：叶子 i 的 fa = i、dep = 0，返回根编号。"""
global node_cnt
node_cnt += 1
p = node_cnt
if l == r:
val[p] = l
return p
mid = (l + r) // 2
ls[p] = build(l, mid)
rs[p] = build(mid + 1, r)
return p
def update(pre: int, l: int, r: int, idx: int, fa: int, dep: int) -> int:
"""在版本 pre 上把下标 idx 的叶子改成 fa|(dep<<20)，返回新版本根。"""
global node_cnt
node_cnt += 1
p = node_cnt
ls[p] = ls[pre]
rs[p] = rs[pre]
if l == r:
val[p] = fa | (dep << 20)
return p
mid = (l + r) // 2
if idx <= mid:
ls[p] = update(ls[pre], l, mid, idx, fa, dep)
else:
rs[p] = update(rs[pre], mid + 1, r, idx, fa, dep)
return p
def query(p: int, l: int, r: int, idx: int) -> int:
"""查询版本 p 中下标 idx 的叶子值（fa | dep<<20）。"""
if l == r:
return val[p]
mid = (l + r) // 2
if idx <= mid:
return query(ls[p], l, mid, idx)
return query(rs[p], mid + 1, r, idx)
def find_root(p: int, n: int, x: int) -> int:
"""沿 fa 链找根，返回根叶子的值。绝不路径压缩：会改写大量历史结点。"""
while True:
v = query(p, 1, n, x)
fa = v & FA_MASK
if fa == x:
return v
x = fa
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
try:
n = next(data)
m = next(data)
except StopIteration:
return
rt = [0] * (m + 1)
rt[0] = build(1, n)
last_ans = 0
out: list[str] = []
for i in range(1, m + 1):
op = next(data)
if op == 1:
a = next(data) ^ last_ans
b = next(data) ^ last_ans
rt[i] = rt[i - 1]
va = find_root(rt[i], n, a)
vb = find_root(rt[i], n, b)
root_a = va & FA_MASK
root_b = vb & FA_MASK
if root_a != root_b:
# 按秩（深度）合并
dep_a = va >> 20
dep_b = vb >> 20
if dep_a < dep_b:
rt[i] = update(rt[i - 1], 1, n, root_a, root_b, dep_a)
elif dep_a > dep_b:
rt[i] = update(rt[i - 1], 1, n, root_b, root_a, dep_b)
else:
tmp = update(rt[i - 1], 1, n, root_a, root_b, dep_a)
rt[i] = update(tmp, 1, n, root_b, root_b, dep_b + 1)
elif op == 2:
k = next(data) ^ last_ans
rt[i] = rt[k] # 回到第 k 次操作之后（k=0 即初始状态）
else:
a = next(data) ^ last_ans
b = next(data) ^ last_ans
root_a = find_root(rt[i - 1], n, a) & FA_MASK
root_b = find_root(rt[i - 1], n, b) & FA_MASK
ans = 1 if root_a == root_b else 0
out.append(str(ans))
last_ans = ans
rt[i] = rt[i - 1]
sys.stdout.write('\n'.join(out) + ('\n' if out else ''))
if __name__ == '__main__':
solve()cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-09 09:30
* update_at: 2026-10-09 11:24
*/
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const int MAXM = 200005;
// 主席树（可持久化线段树）维护数组 fa[]：第 p 个叶子表示元素 p 的父节点与深度
// 每次修改产生 O(log n) 个新结点，历史版本由根编号 rt[] 指向
//
// 空间估算：建树 O(n) 个结点；每个 1 操作产生 O(log n) ~ 18 个结点
// 最坏 m=200000 次合并 => 200000 * 18 = 3.6e6，加上建树与常数余量开 8.5e6
const int MAX_NODES = 8500000;
// 结点：一个对象一个 node[u]，不用平行数组
// val 的位域：低 20 位存 fa（n <= 200000 < 2^20），高 12 位存深度（<= 20 < 2^12）
struct Node {
int left; // 左儿子编号
int right; // 右儿子编号
int val; // 叶子的值：fa | (dep << 20)
};
Node node[MAX_NODES];
int node_cnt = 0; // 已创建结点数，node_cnt 就是最后一个结点编号
int rt[MAXM]; // rt[i] = 第 i 次操作之后的版本根编号
// 新建一个结点，返回编号
int new_node(int left_son, int right_son, int value) {
node_cnt++;
node[node_cnt].left = left_son;
node[node_cnt].right = right_son;
node[node_cnt].val = value;
return node_cnt;
}
// 建初始版本：叶子 i 的 fa = i，dep = 0
int build(int l, int r) {
if (l == r) return new_node(0, 0, l);
int mid = (l + r) >> 1;
int left_son = build(l, mid);
int right_son = build(mid + 1, r);
return new_node(left_son, right_son, 0);
}
// 在版本 pre 的基础上把下标 idx 的叶子改成 fa|(dep<<20)，返回新版本根
int update(int pre, int l, int r, int idx, int fa, int dep) {
if (l == r) return new_node(0, 0, fa | (dep << 20));
int mid = (l + r) >> 1;
int left_son = node[pre].left;
int right_son = node[pre].right;
if (idx <= mid) left_son = update(left_son, l, mid, idx, fa, dep);
else right_son = update(right_son, mid + 1, r, idx, fa, dep);
return new_node(left_son, right_son, 0);
}
// 查询版本 p 中下标 idx 的叶子值（fa|dep）
int query(int p, int l, int r, int idx) {
if (l == r) return node[p].val;
int mid = (l + r) >> 1;
if (idx <= mid) return query(node[p].left, l, mid, idx);
return query(node[p].right, mid + 1, r, idx);
}
const int FA_MASK = (1 << 20) - 1;
// 沿 fa 链找根，返回根叶子的值（含深度）
// 注意：这里绝不能路径压缩——可持久化结构下压缩会改写大量历史结点
int find_root(int p, int n, int x) {
while (true) {
int v = query(p, 1, n, x);
int fa = v & FA_MASK;
if (fa == x) return v;
x = fa;
}
}
void solve() {
int n, m;
if (!(cin >> n >> m)) return;
rt[0] = build(1, n);
int last_ans = 0; // 上一次询问的答案，用于强制在线异或解密
for (int i = 1; i <= m; ++i) {
int op;
cin >> op;
if (op == 1) {
int a, b;
cin >> a >> b;
a ^= last_ans;
b ^= last_ans;
rt[i] = rt[i - 1]; // 未合并时版本不变
int va = find_root(rt[i], n, a);
int vb = find_root(rt[i], n, b);
int root_a = va & FA_MASK;
int root_b = vb & FA_MASK;
if (root_a != root_b) {
// 按秩（深度）合并，保证树深 O(log n)
int dep_a = va >> 20;
int dep_b = vb >> 20;
if (dep_a < dep_b) {
rt[i] = update(rt[i - 1], 1, n, root_a, root_b, dep_a);
} else if (dep_a > dep_b) {
rt[i] = update(rt[i - 1], 1, n, root_b, root_a, dep_b);
} else {
int p = update(rt[i - 1], 1, n, root_a, root_b, dep_a);
rt[i] = update(p, 1, n, root_b, root_b, dep_b + 1);
}
}
} else if (op == 2) {
int k;
cin >> k;
k ^= last_ans;
// 回到第 k 次操作之后的状态：第 0 次操作后就是初始状态
rt[i] = rt[k];
} else {
int a, b;
cin >> a >> b;
a ^= last_ans;
b ^= last_ans;
int root_a = find_root(rt[i - 1], n, a) & FA_MASK;
int root_b = find_root(rt[i - 1], n, b) & FA_MASK;
int ans = (root_a == root_b) ? 1 : 0;
cout << ans << "\n";
last_ans = ans;
rt[i] = rt[i - 1]; // 询问不改变状态
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}复杂度
- 时间复杂度：
建树时间为
。 每次查找根节点的步数不超过 ，每次在线段树上的查询消耗 ，因此 find_root单次耗时。对于 次操作，总时间复杂度为 。 - 空间复杂度：
初始建树需要
个节点，每次合并最多新建常数次线段树路径，产生 个节点，空间复杂度为 。利用压位技巧后，实测最坏需要申请约 的节点数组，占内存 MB，通过 128MB 的空间限制。
总结
- 强制在线的易错点：
last_ans的初值及更新时机非常重要。必须注意：只有 3 操作才刷新last_ans；对于合并操作与回退操作中的参数，一样需要与当前的last_ans异或进行解码，不可遗漏。 - 可持久化数据结构的“均摊陷阱”：此题说明可持久化数据结构并不支持带状态压缩或“改写较长路径”的均摊操作。如果强行引入路径压缩，虽然逻辑成立，但由于每次查询必须产生新版本（由于路径节点更新），极短时间内便会让空间爆表。如果强行不持久化修改以节省空间，则历史状态就遭到了破坏。
k = 0的数据盲区：题目给出回退操作“回到第次操作之后的状态”。若 ，自然对应 rt[0]。但在部分数据中，“的对应处理为退回至 rt[0]”与“忽视不处理当做没发生变化”，在给出的真实数据测试下表现无差别，说明本题数据无法有效区分此边界。但这不代表能够写错语义。相比之下，rt[k]与rt[k-1]间的偏移错误则被真实数据准确卡掉。- 空间与最坏实测情况：实测显示 RSS 峰值在
disjoint3/4点为约 50.5MB（128MB 限制下的 39%），而在特设的“一直构造新支”的极限测试下，最多产生个节点。定义数组上限 MAX_NODES = 8500000充分留有裕度，可安全过关。 - 输出和数据特征：
- 各点输出全是换行符（LF），未包含任何 Windows 换行（CRLF）。
- 输出的行数恰好严格等于操作
3出现的次数。disjoint4是一个极端的边界点：20 万次操作中完全没有回退，查询也只有 1 个，只输出单行的1。 - 不同源的对拍测试：通过在 Python 中维护极慢但
常规版本的 完整快照，600 组随机对拍下与主席树结果达到 0 分歧的三方一致性，充分保证了上述不带路径压缩解法的正确性。 - 强制输出全为
/ 翻转答案等硬编码，以及由于 被破坏产生的各种错误都均被验证器准确捕捉。