学完板子即可开始水紫题
倍增并查集，可以在 \(O(m log^2 n)\) 的时间复杂度内求解 \(m\) 个诸如此类的合并问题：
\[\forall \,\,\,\,\, 0 \leq i \leq k \, , \, merge(x+i,y+i)
\]
就真的是倍增和并查集的结合体，而不像 \(dsu\,on\,tree\) 那样挂个名头
对于这一类问题，我们可以考虑把合并区间进行二进制拆分
給所有长度为 \(2^i\) 的区间开一个并查集（以下统一称为 \(i\) 级并查集）
代表若在 \(i\) 级的并查集中，元素 \(u,v\) 属于同一连通块，则
\[\forall \,\,\,\,\, 0 \leq i < 2^i \, , \, x+i,y+i \text{在同一连通块中}
\]
显然这样的东西非常好维护
再考虑最后怎么把它转成正常并查集的样子
若我想把第 \(i\) 级的并查集传到第 \(i-1\) 级，若 \(p\) 是 \(i\) 级并查级中 \(q\) 的祖先，那么在 \(i-1\) 级并查集中应执行以下操作：
\[merge(q,p),merge(q+2^{i-1},p+2^{i-1})
\]
操作大多数都和 \(st\) 表差不多
luogu P3295
CODE
#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int mod=1e9+7;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
int find_f(int u,int* f){if(f[u]==u) return u;else return f[u]=find_f(f[u],f);
}
void merge(int u,int v,int* f){u=find_f(u,f),v=find_f(v,f);if(u!=v) f[u]=v;
}
int n,m;
int f[21][maxn];
int main(){read(n),read(m);int l1,r1,l2,r2;for(int i=1;i<=n;i++){for(int j=0;j<=20;j++){f[j][i]=i;}}for(int i=1;i<=m;i++){read(l1),read(r1),read(l2),read(r2);for(int j=20;j>=0;j--){if(l1+(1<<j)-1<=r1){merge(l1,l2,f[j]);l1+=(1<<j),l2+=(1<<j);}}}for(int i=20;i>=1;i--){for(int l=1,r=(1<<i);r<=n;l++,r++){int tar=find_f(l,f[i]);merge(l,tar,f[i-1]),merge(l+(1<<(i-1)),tar+(1<<(i-1)),f[i-1]);}}int av=find_f(1,f[0]);LL ans=1;for(int i=1;i<=n;i++){//cout<<find_f(i,f[0])<<' ';if(i==f[0][i]){if(f[0][i]==av) ans=ans*9%mod;else ans=ans*10%mod;}}//cout<<endl;printf("%lld",ans);return 0;
}
//^o^