题解：CF566D Restructuring Company

wsh88 · 2026-08-09 20:10:00 · 题解

思路：

首先我们可以想到用并查集来维护。

我们有三种操作：

• 对于操作一，我们可以直接合并，时间是 O(1) 的。

• 对于操作三，我们直接判断两个数是否在同一个连通块中就可以了。

• 对于操作二，也是最麻烦的操作，我们可以把区间拆开来，把他拆成 (l, l+1),(l+1,l+2),...,(r-1,r) 这几个区间，同时用一个数组记录那些数字已经合并，如果已经合并，就可以直接跳过这些合并过的区间，然后继续拆开区间去合并。

代码也是很简短，直接看吧。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300005;
int n, q;
int fa[maxn], nxt[maxn];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fy] = fx;
}
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        nxt[i] = i + 1;
    }
    int op, x, y;
    while (q--) {
        cin >> op >> x >> y;
        if (op == 1) merge(x, y);
        else if (op == 2){
            int to;
            for (int i = x + 1; i <= y; i = to) {
                merge(i - 1, i);//合并
                to = nxt[i];//往前跳
                nxt[i] = nxt[y];//跳过已合并的区间
            }
        }
        else {
            int fx = find(x), fy = find(y);
            if (fx == fy) cout << "YES" << '\n';
            else cout << "NO" << '\n';
        }
    }
    return 0;
}