我怎么不会烂大街 trick /ll

这个东西显然就是让你用并查集来维护的，考虑要怎么维护，暴力显然只能做到 $O(nq)$。

有效合并只有 $n-1$ 次，相同连通块自己合并自己带来了巨大的不必要时间开销，考虑压掉但是思考半天发现非常困难，逃跑。

这样，我们类似 ST 表的给并查集的父亲数组定义成 $fa_{i,j}$，表示 $[j,j+2^i)$ 和 $[fa_{i,j},fa_{i,j}+2^i)$ 顺着过去对应位置相等。

然后，我们考虑倒着转移 ST 表，显然每个 $fa_i$ 里的边都可以分裂成两条 $fa_{i-1}$ 里的边，于是直接做就好了。

每次输入我们都可以拆成 $\log n$ 条边分别存储在不同的 $fa_i$ 里，最后按照上面的方式转移到 $fa_0$ 里就得到了最原始的并查集。

于是我们得到了 $O(n\log n)$ 做法。

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int fa[25][500005];
int find(int op,int x){
    return fa[op][x]==x?x:fa[op][x]=find(op,fa[op][x]);
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=20;i++)
    for(int j=1;j<=n;j++)
    fa[i][j]=j;
    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>l2;
        int siz;
        cin>>siz;
        for(int i=20;i>=0;i--)
        if((1<<i)&siz){
            fa[i][find(i,l1)]=find(i,l2);
            l1+=1<<i;
            l2+=1<<i;
        }
    }
    for(int i=20;i;i--){
        for(int j=1;j+(1<<i)-1<=n;j++)
        fa[i-1][find(i-1,j)]=find(i-1,find(i,j)),
        fa[i-1][find(i-1,j+(1<<(i-1)))]=find(i-1,find(i,find(i,j)+(1<<(i-1))));
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    if(i==find(0,i))ans++;
    cout<<ans;
    return 0;
}
// 我需要好好计算一下能不能顺利中和自由落体的速度啊。
// 毕竟，如果没能完全中和掉的话
// 恐怕我们就会变成一团肉饼了。

// 这人好像在说什么恐怖的话？！