cf566D Restructing Company

给定数组a[n]，初始时a[i]=i，有q次操作：
操作1、1 x y，表示合并x和y
操作2、2 x y，表示合并区间[x,y]
操作3、3 x y，表示询问x和y是否在同一个集合
1<=n<=2E5; 1<=q<=5E5

分析：可以用set+并查集来做，这里用区间并查集来做，在普通并查集的基础上增加ne变量，来维护下一个没合并的位置，用于操作2时快速跳过已合并的点。

#include <bits/stdc++.h>
using i64 = long long;

const int N = 200005;
int n, q, fa[N], ne[N];

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

void join(int x, int y) {
   x = find(x);
   y = find(y);
   if (x != y) {
      fa[x] = y;
   }
}

void solve() {
   int n, q;
   std::cin >> n >> q;
   for (int i = 1; i <= n; i++) {
      fa[i] = ne[i] = i;
   }
   for (int i = 0; i < q; i++) {
      int op, x, y;
      std::cin >> op >> x >> y;
      if (op == 1) {
         join(x, y);
      } else if (op == 2) {
         while (x < y) {
            x = next(x);
            if (x < y) {
               join(x, y);
               ne[x] += 1;
            }
         }
      } else if (op == 3) {
         if (find(x) == find(y)) {
            std::cout << "YES\n";
         } else {
            std::cout << "NO\n";
         }
      }
   }
}

int main() {
   std::cin.tie(0)->sync_with_stdio(0);
   int t = 1;
   while (t--) solve();
   return 0;
}