TaopiTTT

對于操作:將一段元素合并為同類。

在合并 \([l,r]\) 這一段數的時候，其實有很多數本來就在一個并查集里。我們只需要合并若干個還沒有合并的并查集，而不需要從 \(l\) 到 \(r\) 一個一個合并。因為只要合并了這幾個并查集，效果等價于把 \([l,r]\) 直接合并了。

實現方法：每次記錄一個 \(nxt[i]\) 表示第 \(i\)個點后面第一個沒有和 \(i\) 合并的點。每次合并的時候直接 $i=nxt[i] $處理即可，最后把 $[l,r] $中所有的 nxt[i] 都賦值為 \(nxt[r]\)。這樣的話，兩個不同的并查集在這一操作中至多合并一次。
https://codeforces.com/problemset/problem/566/D

#include<bits/stdc++.h>
#define endl '\n'
#define lowbit(x) (x&-x)
using namespace std;
const double pi=acos(-1);
const int N=2e5+5;
int fa[N],nx[N];

int find(int i){
	if(i!=fa[i]) fa[i]=find(fa[i]);//路徑壓縮
    return fa[i];
}

void join(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return;
    if(u<v) swap(u,v);
    fa[v]=u;
}

void solve(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=n+1;i++){
        fa[i]=i;
        nx[i]=i+1;
    }
    while(q--){
        int op;cin>>op;
        int x,y;cin>>x>>y;
        if(op==3){
            x=find(x);
            y=find(y);
            if(x==y) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        if(op==1){
            join(x,y);
        }
        if(op==2){
            int ty=find(y);
            for(int i=x;i<=y;){
                int t=i;
                i=nx[i];
                fa[find(t)]=ty;
                nx[t]=nx[y];
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}