一个长度为n的大数，用S1S2S3...Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...Sr2完全相同。比如n=6时，某限制条件l1=1，r1=3，l2=4，r2=6，那么123123，351351均满足条件，但是12012，131141不满足条件，前者数的长度不为6，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Solution
涨姿势了。
不难想到用并查集维护数字之间的相等关系，最后用联通块个数统计答案。
但这样的复杂度是n^2的，需要去优化它，
考虑到每次合并都是两段等长的区间进行合并，所以我们考虑使用倍增。
我们开nlogn个并查集，num[i][j]表示从i开始的2^j个数，每次区间合并我们把它拆成logn个区间分别合并。
最后自顶向底合并儿子，就像线段树一样，
Code
#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
typedef long long ll;
const int mod=1e9+;
int num[N][],f[N*],n,m,tot,son[N*][],l1,r1,l2,r2;
int find(int x){return f[x]=f[x]==x?x:find(f[x]);}
long long power(ll x,int y){
ll ans=;
while(y){
if(y&)(ans*=x)%=mod;
(x*=x)%=mod;
y>>=;
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;(<<i)<=n;++i)
for(int j=;j+(<<i)-<=n;++j){
num[j][i]=++tot;f[tot]=tot;
if(i){
son[tot][]=num[j][i-];
son[tot][]=num[j+(<<i-)][i-];
}
}
for(int i=;i<=m;++i){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int len=r1-l1+;
for(int j=;j>=;--j)
if((<<j)<=len){
int x=find(num[l1][j]),y=find(num[l2][j]);
if(x!=y)f[x]=y;
len-=(<<j);l1+=(<<j);l2+=(<<j);
}
}
for(int i=;i>=;--i)
for(int j=;j+(<<i)-<=n;++j){
int root=num[j][i];
if(find(root)!=root){
int x=find(son[root][]),y=find(son[f[root]][]);
if(x!=y)f[x]=y;
x=find(son[root][]),y=find(son[f[root]][]);
if(x!=y)f[x]=y;
}
}
int ans=;
for(int i=;i<=n;++i)if(find(num[i][])==num[i][])ans++;
printf("%lld",*power(,ans-)%mod);
return ;
}