DSU on array 是一种把并查集用于一维数组上的技巧，用来维护数组中下一处未处理的位置。简单的说，如果某个位置 \(i\) 已被处理，我们希望下一次访问它时自动跳转到下一个没有被处理的位置 \(j\)。
1 - 适用场景
场景 1 区间赋值（未被赋值的位置）
- 给 \([l, r]\) 内未被处理过的点赋值（染色、标记、填数）
场景 2 区间删除
-
删除 \([l, r]\) 中所有仍存在的点
-
后续查询要跳过已经删除的节点
场景 3 击败 / 消灭模型
- 如：winner 在区间内存活，其他人都被淘汰
场景 4 寻找区间内下一位置
-
寻找区间内第一个“未覆盖”位置
-
区间被划分、覆盖后需要跳过已覆盖点
场景 5 离线模拟多次区间处理
- 处理区间顺序已知，适合用 DSU 做快速跳跃
2 - 常用模板
初始化及函数：
// 初始化 fa[i] = i;
vector<int> fa(n + 2);
iota(fa.begin(), fa.end(), 0);// 找到 x 的下一个还未处理的位置。
function<int(int)> find = [&](int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]];return x;
};// 删除该位置，即将 fa[x] 设为下一个还未处理的位置。
function<void(int)> erase = [&](int x) {fa[x] = find(x + 1);
};
遍历方式：
int cur = find(l);
while (cur <= r) {/* 代码块 */erase(cur);cur = find(cur);
}
3 - 例题 - CF356A
题目大意：
有 \(n\) 个从 \(1-n\) 编号的骑士，现在要在他们之间进行总共 \(m\) 场比赛。第 \(i\) 场比赛会在 \([l_i, r_i]\) 编号的骑士之间进行，并决出一位胜者 \(x_i\)，其他骑士会出局并无法参加接下来的比赛。最后留下的骑士就是比赛的最终胜者。请你输出比赛结束后每一位骑士都被哪一位骑士击败了。
思路：
首先思考朴素解法，每次比赛的时候我们会遍历 \([l_i, r_i]\) 并处理此前没有被击败的骑士，这种解法复杂度为 \(O(n^2)\) 明显无法通过大数据范围。
而题意明显符合 DSU on array 的击败模型，因此我们考虑使用 DSU 来跳过每回合被击败的骑士，此时时间复杂度优化至 \(O((n + m) \alpha (n))\)，其中 \(n\) 为骑士数量，\(m\) 为询问次数。因为 \(\alpha (n)\) 为阿克曼反函数，因此整体时间复杂度近似 \(O(n + m)\)。具体实现参考代码。
code：
#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define i64 long longint main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int n, m;cin >> n >> m;vector<int> fa(n + 2);iota(fa.begin(), fa.end(), 0);function<int(int)> find = [&](int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]];return x;};function<void(int)> erase = [&](int x) {fa[x] = find(x + 1);};vector<int> ans(n + 1);for (int i = 1; i <= m; i ++ ) {int l, r, winner;cin >> l >> r >> winner;if (l > r) swap(l, r);for (int j = find(l); j <= r; j = find(j) /* 跳转至下一个未处理的位置 */) {// 跳过 winnerif (j == winner) {j = find(j + 1);continue;}// 赋值答案并删除 jans[j] = winner;erase(j);}}for (int i = 1; i <= n; i ++ ) {cout << ans[i] << ' ';}
}