题解：CF566D Restructuring Company

TLEZPB · 2024-12-24 13:38:08 · 题解

Restructuring Company

前言

老师不知道什么原因把这题丢到了链表专题里。

思路

第 1，3 操作可以直接用并查集搞定。

2 操作如果暴力合并会让时间复杂度飙升到 O(nq) 导致 TLE，我们考虑优化。

经过观察可以发现把一段区间合并后会让让序列产生一些连续的段，于是我们可以用链表的思想给每个点一个下一个点，这样在进行二操作时就可以每次往右跳而不是一个一个找。

AC code

CF AC 记录。

#include <iostream>
#define endl '\n'
using namespace std;

const int N = 2e5 + 5;

int fa[N], r[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
        r[i] = i + 1;
    }
    while(q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1) {
            int u = find(x), v = find(y);
            fa[u] = v;
        }
        else if(op == 2) {
            for(int i = x + 1; i <= y;) {
                int u = find(i - 1), v = find(i);
                fa[u] = v;
                int i2 = r[i];
                r[i] = r[y];
                i = i2;
            }
        }
        else {
            int u = find(x), v = find(y);
            if(u == v) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}