Description
一个长度为 (n) 的大数，用 (S1S2S3...Sn) 表示，其中 (Si) 表示数的第 (i) 位, (S1) 是数的最高位，告诉你一些限制条件，每个条件表示为四个数，(l1)，(r1)，(l2)，(r2)，即两个长度相同的区间，表示子串 (Sl1) (Sl1+1) (Sl1+2) (...) (Sr1) 与 (Sl2) (Sl2+1) (Sl2+2) (...) (Sr2) 完全相同。比如 (n=6) 时，某限制条件 (l1=1)，(r1=3)，(l2=4)，(r2=6) ，那么123123，351351均满足条件，但是12012，131141不满足条件，前者数的长度不为6，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Input
第一行两个数 (n) 和 (m) ，分别表示大数的长度，以及限制条件的个数。接下来 (m) 行，对于第 (i) 行,有 4 个数 (li1)，(ri1)，(li2)，(ri2) ，分别表示该限制条件对应的两个区间。
(1 leq n leq 10^5)，(1 leq m leq 10^5)，(1 leq li1,ri1,li2,ri2 leq n)；并且保证 (ri1-li1=ri2-li2) 。
Output
一个数，表示满足所有条件且长度为 (n) 的大数的个数，答案可能很大，因此输出答案模 (10^9+7) 的结果即可。
Sample Input
4 2
1 2 3 4
3 3 3 3
Sample Output
90
想法
一个显然的想法是，暴力用并查集把一样的位置并起来
最后查询有多少个并查集，设有 (x) 个，则最终答案是 (9 imes 10^{n-1}) （最高位不能为零）
但显然超时。
考虑怎么优化连边——倍增。
注意到上面连的边数过多的原因是有许多无用边（比如可能有许多边的作用都是让 (u) 与 (v) 连起来；或者一个大小为 (n) 的并查集中有用边只有 (n-1) 条，却在内部连了很多条边）
那有一种极巧妙的做法是加一些新点代表一个个长度为 (2^i) 的区间，有点类似 (ST) 表
每次合并把 ([l,r]) 拆成 (O(logn)) 段区间，把代表那些区间的点对应并起来
最后下放。如原本代表 ([l1,r1]) 与 ([l2,r2]) 的点在一个并查集中，那么将 ([l1,(l1+r1)>>1]) 与 ([l2,(l2+r2)>>1]) 并起来，将 ([(l1+r1)>>1+1，r1]) 和 ([(l2+r2)>>1+1，r2]) 并起来即可
下放的总复杂度是 (O(nlogn)) 的
下放到最后就是代表长度为1的区间的点了，找一下并查集个数就可以了。
总复杂度 (O(logn))
太巧妙了！神仙方法 (orz)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define P 1000000007
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 100005;
int n,m;
int f[N][18],cnt,ch[18*N][2],fa[N*18];
int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]) ; }
void unit(int x,int y){
x=getfa(x); y=getfa(y);
if(x!=y) fa[x]=y;
}
int Pow_mod(int x,int y){
int ret=1;
while(y){
if(y&1) ret=1ll*ret*x%P;
x=1ll*x*x%P;
y>>=1;
}
return ret;
}
int main()
{
n=read(); m=read();
int l1,l2,r1,r2;
for(int j=0;j<18;j++){
int l=(1<<j);
for(int i=1;i+l-1<=n;i++){
f[i][j]=++cnt;
if(j==0) continue;
ch[cnt][0]=f[i][j-1]; ch[cnt][1]=f[i+(l>>1)][j-1];
}
}
for(int i=1;i<=cnt;i++) fa[i]=i;
while(m--){
l1=read(); r1=read(); l2=read(); r2=read();
for(int i=17;i>=0;i--){
if(l1+(1<<i)-1>r1) continue;
unit(f[l1][i],f[l2][i]);
l1+=(1<<i); l2+=(1<<i);
}
}
for(int i=cnt;i>n;i--)
if(fa[i]!=i){
unit(ch[fa[i]][1],ch[i][1]);
unit(ch[fa[i]][0],ch[i][0]);
}
int ans=0;
for(int i=1;i<=n;i++) if(fa[i]==i) ans++;
printf("%d
",1ll*9*Pow_mod(10,ans-1)%P);
return 0;
}