题目
题目描述
一个长度为 $n$ 的大数，用 $S_1S_2S_3 \cdots S_n$表示，其中 $S_i$ 表示数的第 $i$ 位, $S_1$ 是数的最高位。告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}$完全相同。 比如 $n=6$ 时，某限制条件 $l_1=1,r_1=3,l_2=4,r_2=6$ ，那么 $123123$，$351351$ 均满足条件，但是 $12012$，$131141$ 不满足条件，前者数的长度不为 $6$ ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
输入输出格式
输入格式：
第一行两个数n和m，分别表示大数的长度，以及限制条件的个数。
接下来m行，对于第i行,有4个数 li1，ri1，li2，ri2，分别表示该限制条件对应的两个区间。
$1\le n\le 10^5$，$1\le m\le 10^5$ ，$1\le li1,ri1,li2,ri2 \le n$ ；并且保证 $ri1-li1=ri2-li2$ 。
输出格式：
一个数，表示满足所有条件且长度为n的大数的个数，答案可能很大，因此输出答案模 $10^9+7$ 的结果即可。
输入输出样例
输入样例#1：
4 2
1 2 3 4
3 3 3 3
输出样例#1：
90
题解
暴力是$O(nm\alpha)$的，即把所有区间的点都用并查集连起来
考虑怎么优化
$f_{i,j}$表示点$i$往后延伸$2^j$位代表区间的编号（新定义）
把一个区间拆成$\log$个子区间（倍增的思路），然后把这些子区间用并查集合起来
这样就能$O(\alpha\log n)$加入区间了，至于查询答案，把长度为$2^j$的区间拆成两个长度为$2^{j-1}$的区间处理即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,mod=1e9+7;
int n,m,tot,ans;
int fa[MAX*18];
int f[18][MAX];
bool use[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void Merge(int x,int y)
{
int r1=find(x),r2=find(y);
if(r1!=r2) fa[r1]=r2;
}
void Solve(int l1,int l2,int d)
{
for(int i=17;i>=0;--i)
if(d&(1<<i)) Merge(f[i][l1],f[i][l2]),l1+=(1<<i),l2+=(1<<i);
}
int Pow(int b)
{
int ans=1,a=10;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) ans=1ll*ans*a%mod;
return ans;
}
int main()
{
n=read(),m=read();
for(int i=0;i<=17;++i)
for(int j=1;j<=n;++j)
f[i][j]=++tot;
for(int i=1;i<=tot;++i)
fa[i]=i;
for(int i=1,l1,r1,l2,r2;i<=m;++i)
l1=read(),r1=read(),l2=read(),r2=read(),Solve(l1,l2,r1-l1+1);
for(int i=17;i>=1;--i)
for(int j=1,r1,x1,x2;j<=n;++j)
if(find(f[i][j])!=f[i][j]) r1=find(f[i][j]),x1=(r1%n)?r1%n:n,Merge(f[i-1][j],f[i-1][x1]),Merge(f[i-1][j+(1<<i-1)],f[i-1][x1+(1<<i-1)]);
for(int i=1,r1,x;i<=n;++i)
{
r1=find(f[0][i]),x=(r1%n)?r1%n:n;
if(!use[x]) use[x]=1,++ans;
}
return printf("%d",1ll*9*Pow(ans-1)%mod),0;
}
