题意：长为$n \le 10^5$的数字，给出$m \le 10^5$个限制$[l1,r1]\ [l2,r2]$两个子串完全相等，求方案数
把所有要求相等的位置连起来，不就是$9*10^{连通块个数}$嘛
但是最坏情况要连$nm$次啊
有很多都是重复的太浪费了
于是各种乱搞，甚至想了一下分块，即使能减少边的条数也不能减少计算时会走的边的次数
然后看题解，竟然是用倍增来优化
有道理啊，分块太死板了，倍增的话就可以灵活的得到每个区间
$fa[i][j]$表示从i开始$2^j$个数的区间的父亲(也就是和$fa[i][j]$开始$2^j$个数完全相等)
合并的时候从高层往低层合并(j大到小)，遇到fa相同就停下
貌似一次合并最坏也是$O(n)$啊
这里卡了我好久. 每层最多合并$n$次，一共$logn$层，没问题啊
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+, P=1e9+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int n, m, l1, r1, l2, r2;
int fa[N][], Log[N];
int find(int i, int j) {return i==fa[i][j] ? i : fa[i][j]=find(fa[i][j], j);}
void Union(int x, int y, int j) {
int f1=find(x, j), f2=find(y, j);
if(f1==f2) return;
fa[f1][j]=f2;
if(j) Union(x, y, j-), Union(x + (<<(j-)), y+ (<<(j-)), j-);
}
ll Pow(ll a, int b) {
ll ans=;
for(; b; b>>=, a=a*a%P)
if(b&) ans=ans*a%P;
return ans;
} int main() {
freopen("in","r",stdin);
n=read(); m=read();
if(n==) {puts(""); return ;}
Log[]=;
for(int i=; i<=n; i++) Log[i]=Log[i>>]+;
for(int i=; i<=n; i++)
for(int j=; j<=; j++) fa[i][j]=i;
for(int i=; i<=m; i++) {
l1=read(), r1=read(), l2=read(), r2=read();
int t=Log[r1-l1+];
Union(l1, l2, t); Union(r1-(<<t)+, r2-(<<t)+, t);
}
int ans=;
for(int i=; i<=n; i++) ans += find(i, )==i;
printf("%lld\n", *Pow(, ans-)%P);
}