下决心写一道题写一篇题解。
考虑暴力，直接并查集合并相同的数，和今天T1一样。
考虑优化这个暴力。因为今天T1题解说要倍增，所以考虑一个长的跟ST表一样的倍增。
具体的，我们对每个位置开个长的跟ST表一样的东西。也就是 \(id[i][j]\) 代表 \(i\) 为左端点长度为 \(2^j\) 的情况。然后每次给你一个区间，把区间长度二进制拆分，对应位置合并，这样单次修改就是 \(O(\log n)\) 的。查询的时候直接从大到小扫段长，把长段对半分成两个短段就行了。
最后统计有多少个不一样的记作 \(cnt\) ，答案就是 \(9\times 10^{cnt-1}\) （因为开头不能是 \(0\) ）。
看代码吧。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int mod=1000000007;
int n,m,num,cnt;
int fa[100010*20],id[100010][20];
bool v[100010];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x);y=find(y);fa[y]=x;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=__lg(n);i++){
for(int j=1;j<=n;j++){
id[j][i]=++num;fa[id[j][i]]=num;//初始化并查集
}
}
for(int i=1;i<=m;i++){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int len=r1-l1+1;
for(int k=__lg(n);k>=0;k--){//从大到小二进制拆分段长
if(l1+(1<<k)-1<=r1){
merge(id[l1][k],id[l2][k]);
l1+=(1<<k);l2+=(1<<k);//合并对应位置
}
}
}
for(int j=__lg(n);j>=1;j--){
for(int i=1;i+(1<<j)-1<=n;i++){
int x=find(id[i][j]);
if(x==id[i][j])continue;
x%=n;if(!x)x=n;//找到对应的左端点x
merge(id[x][j-1],id[i][j-1]);
merge(id[x+(1<<(j-1))][j-1],id[i+(1<<(j-1))][j-1]);//分成两端合并
}
}
for(int i=1;i<=n;i++){
int x=find(id[i][0]);
x%=n;if(!x)x=n;//统计答案
if(!v[x]){
v[x]=true;cnt++;
}
}
printf("%lld\n",9ll*qpow(10,cnt-1)%mod);
return 0;
}