在网上胡乱找的一些关于并查集处理区间跳跃（也有叫区间覆盖/序列联通性，这类问题有没有什么统一叫法存疑？）的题目，或许能学习后成为一种套路
参考：
Knight Tournament
板子题
维护一个并查集\(nxt\)，\(nxt[i]\)为从\(i\)开始（包含\(i\)）的第一个没有被打败的骑士的编号
并查集初始化的时候记得到多初始化一个到\(nxt[n+1]\)
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int nxt[N], ans[N];
int find(int x) {
if (x != nxt[x]) nxt[x] = find(nxt[x]);
return nxt[x];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n + 1; ++ i) nxt[i] = i;
while (m -- ) {
int l, r, x;
cin >> l >> r >> x;
for (int i = find(l); i <= r; i = find(i)) {
if (i != x) {
ans[i] = x;
nxt[i] = i + 1;
}
else i = i + 1;
}
}
for (int i = 1; i <= n; ++ i) cout << ans[i] << ' ';
return 0;
}
疯狂的馒头/白雪皑皑
后面的操作会覆盖前面的操作，考虑可以倒着染色，思路跟上题一样，依旧是板子题
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int nxt[N], ans[N];
int find(int x) {
if (nxt[x] != x) nxt[x] = find(nxt[x]);
return nxt[x];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, p, q;
cin >> n >> m >> p >> q;
for (int i = 1; i <= n + 1; ++ i) nxt[i] = i;
for (int i = m; i; -- i) {
int l = (i * p + q) % n + 1;
int r = (i * q + p) % n + 1;
if (l > r) swap(l, r);
for (int j = find(l); j <= r; j = find(j)) {
ans[j] = i;
nxt[j] = j + 1;
}
}
for (int i = 1; i <= n; ++ i) cout << ans[i] << '\n';
return 0;
}
Two Teams
分别用并查集维护从\(i\)开始从左往右第一个没有被选择的人的编号和从右往左第一个没有被选择的人的编号
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], ans[N], idx[N];
struct DSU {
int fa[N];
DSU() {
iota(fa, fa + N, 0);
}
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int a, int b) {
int p = find(a), q = find(b);
fa[p] = q;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
idx[a[i]] = i;
}
DSU pre, nxt;
int maxv = n, tag = 1;
while (1) {
while (ans[idx[maxv]]) -- maxv;
if (!maxv) break;
int pos = idx[maxv];
ans[pos] = tag;
pre.merge(pos, pos - 1);
nxt.merge(pos, pos + 1);
int i = pre.find(pos), cnt = 0;
while (i >= 1 && cnt < k) {
ans[i] = tag;
pre.merge(i, i - 1);
nxt.merge(i, i + 1);
++ cnt;
i = pre.find(i);
}
i = nxt.find(pos), cnt = 0;
while (i <= n && cnt < k) {
ans[i] = tag;
pre.merge(i, i - 1);
nxt.merge(i, i + 1);
++ cnt;
i = nxt.find(i);
}
tag = 3 - tag;
}
for (int i = 1; i <= n; ++ i) cout << ans[i];
return 0;
}
Professor Higashikata
思路参考：
Codeforces Round 882 (Div. 2)（A-D，待更新）
Codeforces Round 882 (Div. 2) A - D, F
\(t(s)\)中越靠前的位置为\(1\)，字典序也相应越大，想到\(s[i]\)在 \(t(s)\)中的位置越前，将其变为1的贡献也越大
考虑维护\(s[i]\)在\(t(s)\)中第一次出现的位置，并按出现位置的先后对\(i\)排序，顺序越前的\(i\)越优先将\(s[i]\)变为\(1\)，维护第一次出现的位置的过程使用并查集，后续用树状数组，详细可以见上面两篇博客
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, q, idx[N];
int fa[N], fen[N];
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int a, int b) {
int p = find(a), q = find(b);
fa[p] = q;
}
int lowbit(int x) { return x & -x; }
void modify(int x, int d) {
while (x <= n) fen[x] += d, x += lowbit(x);
}
int query(int x) {
int ans = 0;
while (x) ans += fen[x], x -= lowbit(x);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
string s;
cin >> s;
s = ' ' + s;
for (int i = 1; i <= n + 1; ++ i) fa[i] = i;
int tot = 0;
for (int i = 1; i <= n; ++ i)
if (s[i] == '1') ++ tot;
int cnt = 0;
for (int i = 1; i <= m; ++ i) {
int l, r;
cin >> l >> r;
for (int j = find(l); j <= r; j = find(j)) {
idx[j] = ++ cnt;
if (s[j] == '1') modify(idx[j], 1);
merge(j, j + 1);
}
}
while (q -- ) {
int x;
cin >> x;
if (s[x] == '1') {
s[x] = '0';
-- tot;
if (idx[x]) modify(idx[x], -1);
}
else {
s[x] = '1';
++ tot;
if (idx[x]) modify(idx[x], 1);
}
if (cnt <= tot) cout << cnt - query(cnt) << '\n';
else cout << tot - query(tot) << '\n';
}
return 0;
}