题意
做法
先说普通(O(n^2))做法。
就是把相同的数字暴力合并，然后计算联通块个数(cnt)，然后答案就是(10^{cnt-1}*9)。
但是呢，这样合并太太太太慢了，比如说([l,r])这个区间等于([q,p])，然后([l,r])又等于([frac{q+p}{2},?])，这样子的话，我们会跑(2(r-l+1))，但事实上，我们会发现，([l,frac{l+r}{2}],[frac{l+r}{2}+1,r],[q,frac{q+p}{2}],[frac{q+p}{2}+1,p],[p+1,?])这五个区间全部都是一样的，然后就只用跑(frac{5}{2}(r-l+1))，额，貌似还更慢了。。。但是如果这样子的区间越来越多，你就会发现，其会越来越快。
因此不妨设(fa[i][j])为([j,j+2^{i}))区间的并查集父亲。
然后采用类似(ST)表的操作，不过是反向的，(ST)表是知道下面信息往上传，而这里是知道上面信息往下传。
时间复杂度：(O(nlog^2n))。
#include<cstdio>
#include<cstring>
#define N 110000
#define SN 20//16
using namespace std;
typedef long long LL;
const LL mod=1000000007;
inline int findfa(int x,int *fa)
{
if(fa[x]!=x)fa[x]=findfa(fa[x],fa);
return fa[x];
}
inline int mymin(int x,int y){return x<y?x:y;}
inline void mer(int x,int y,int *fa)
{
int tx=findfa(x,fa),ty=findfa(y,fa);
if(tx>ty)tx^=ty^=tx^=ty;
if(tx!=ty)fa[ty]=tx;
}
inline LL ksm(LL x,int y)
{
LL ans=1;
while(y)
{
if(y&1)ans=(ans*x)%mod;
x=(x*x)%mod;y>>=1;
}
return ans;
}
int fa[SN][N],lo2[N];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)lo2[i]=lo2[i>>1]+1;
for(int i=1;i<=n;i++)
{
for(int j=lo2[n-i+1];j>=0;j--)fa[j][i]=i;
}
for(int i=1;i<=m;i++)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
while(l1<=r1)
{
int k=lo2[r1-l1+1];
mer(l1,l2,fa[k]);
l1+=(1<<k);
l2+=(1<<k);
}
}
for(int i=lo2[n];i>=1;i--)
{
for(int j=n-(1<<i)+1;j>=1;j--)
{
findfa(j,fa[i]);//事实上这个可以去掉，因为合并是把大的合并到小的里面
mer(j,fa[i][j],fa[i-1]);mer(j+(1<<(i-1)),fa[i][j]+(1<<(i-1)),fa[i-1]);
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(findfa(i,fa[0])==i)cnt++;
}
LL ans=(ksm(10,cnt-1)*9)%mod;
printf("%lld
",ans);
return 0;
}
或许你会问，我怎么知道什么时候要用到倍增啊？？？？
这里放上https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p3295大佬对于倍增使用的讲解。
倍增
其实倍增法不仅局限于快速幂，后缀数组，ST表，求lca之类的特定算法，而是用来解决一类特定问题的。
倍增原理
看似玄学的倍增其实源于两个数学等式
1.2^n=2^(n-1)+2^(n-1)
2.N=sigma(pi*2^i) [i∈(0,+∞)] {中pi为N的二进制第i位}
想必任何一个知道二进制的人都明白上述两个等式吧……
而倍增法的唯一要求的是，被称之为“+”的运算满足结合律(有些人也成操作满足可合并性)
具体来讲，倍增法用到的地方一般是，我们现在要询问/修改一些东西，然后我们发现操作具有合并性，之后呢，我们对于每个大小为2^i的东西预处理出来一个答案，等到询问的时候，就将询问的东西大小用二进制表达，将预处理出来的每个东西合并起来就得到了答案
常用的两类二进制拆分代码
for(int i=0;p;p>>=1,i++){/*do sth*/}
for(int i=20;p>0;i--){if(p>po[i]){p-=po[i]}/*do sth*/}
其中上面一个适用于p已知的情况(比如倍增求lca，跳到深度相等的那段代码)
下面的一个适用于p未知，但是可以比较p和某个值的大小，以及可以做相减运算 (比如lca第二段，两个点一起向上跳，但是不知道lca的深度的情况，但是我们用这个代码在未知lca深度的情况下对lca深度做了二进制拆分)
然后我们来结合这道题讲一下如何魔改倍增法，因为这个玩意和dp，分治法都很像，都是根据某一个问题的性质设计了类似的"方法"，根本不是有板子的算法，所以我们要具体问题具体分析……
然后后面就是题解了。