题解：
学习了一下区间并查集的姿势
区间并查集模板题
考虑暴力并查集维护相同的数字，方案数就是9*10^(cnt-1) （cnt为连通块个数）
然后考虑用ST表的方式维护并查集
fa[x][k]=y表示[x,x+(1<<k)-1]的区间与[y,y+(1<<k)-1]完全相同
每次merge一下就好了
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define maxn 100005 4 using namespace std; 5 const ll mod = 1000000007; 6 int n,m; 7 int fa[20][maxn]; 8 int find(int k,int x) 9 { 10 if(fa[k][x]==x)return x; 11 return fa[k][x]=find(k,fa[k][x]); 12 } 13 void merge(int k,int x,int y) 14 { 15 int fx=find(k,x),fy=find(k,y); 16 if(fx==fy)return; 17 fa[k][fx]=fy; 18 if(!k)return; 19 merge(k-1,x,y); 20 merge(k-1,x+(1<<(k-1)),y+(1<<(k-1))); 21 } 22 int main() 23 { 24 scanf("%d%d",&n,&m); 25 for(int j=18;j>=0;--j) 26 for(int i=1;i<=n;++i)fa[j][i]=i; 27 for(int i=1;i<=m;++i) 28 { 29 int l1,r1,l2,r2; 30 scanf("%d%d%d%d",&l1,&r1,&l2,&r2); 31 int k=(int)(log2((double)(r1-l1+1))); 32 merge(k,l1,l2); 33 merge(k,r1-(1<<k)+1,r2-(1<<k)+1); 34 } 35 int cnt=0; 36 for(int i=1;i<=n;++i)if(find(0,i)==i)cnt++; 37 ll ans=9; 38 for(int i=1;i<=cnt-1;++i)ans=ans*10%mod; 39 printf("%lld ",ans); 40 return 0; 41 }