CFR 556 D. Restructuring Company ( Union Find )

Problem - 566D - Codeforces

題意：
給你 N 個人，初始時他們自己一個組。
Q 筆詢問，三種形式：
1 x y：merge( x, y )
2 x y：merge( x, x + 1, ..., y )
3 x y：print "YES" if group( x ) == group( y ) else "NO"

制約：
1 ≤ N ≤ 2e5
1 ≤ Q ≤ 5e5

解法：
作為效率瓶頸的第二種詢問，有連續性。
換句話說，如果當做第一種詢問是不存在的，一個群只會在一個連續區間裡。
因此可以記錄一個 nxt 陣列，nxt[ i ] 代表 i 右邊第一個不屬於群 group( i ) 的元素位置。
顯然，只要每次讓指針移動到 nxt[ 指針 ]，如此合併，至多只能合併 N 次，之後大家就團結了。
至於這個陣列的維護，只要在詢問 2 的時候進行就可以了，因為少維護 nxt 對正確性不會有影響。

複雜度：
O( N lg N + Q )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 2e5 );

int N, Q;

int fa[ MAXN ];
int nxt[ MAXN ];

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

void unite( int x, int y ) {
  fa[ find( x ) ] = find( y );
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> Q;
  for( int i = 0; i < N; ++i ) {
    fa[ i ] = i;
    nxt[ i ] = i + 1;
  }
  for( int qi = 0; qi < Q; ++qi ) {
    int op, x, y;
    cin >> op >> x >> y;
    --x, --y;
    switch( op ) {
      case 1:
        unite( x, y );
        break;
      case 2:
        for( int i = x; i <= y; ) {
          unite( x, i );
          int tmp = nxt[ i ];
          nxt[ i ] = nxt[ y ];
          i = tmp;
        }
        break;
      case 3:
        cout << ( find( x ) == find( y ) ? "YES" : "NO" ) << "\n";
        break;
    }
  }
  return 0;
}