题面
题目描述
一个长度为 \(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}S\) 完全相同。
比如 \(n=6\) 时，某限制条件 \(l_1=1,r_1=3,l_2=4,r_2=6\) ，那么 \(123123\) ， \(351351\) 均满足条件，但是 \(12012\) ， \(131141\) 不满足条件，前者数的长度不为 \(6\) ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
输入输出格式
输入格式：
第一行两个数 \(n\) 和 \(m\) ，分别表示大数的长度，以及限制条件的个数。
接下来 \(m\) 行，对于第 \(i\) 行,有 \(4\) 个数 \(l_{i1},r_{i1},l_{i2},r_{i2}\) ，分别表示该限制条件对应的两个区间。
\(1\le n\le 10^5\) ， \(1\le m\le 10^5\) ， \(1\le l_{i1},r_{i1},l_{i2},r_{i2} \le n\) ；并且保证 \(r_{i1}-l_{i1}=r_{i2}-l_{i2}\) 。
输出格式：
一个数，表示满足所有条件且长度为n的大数的个数，答案可能很大，因此输出答案模 \(10^9+7\) 的结果即可。
输入输出样例
输入样例：
4 2
1 2 3 4
3 3 3 3
输出样例：
90
思路
首先想到一个 \(O(m \times n^2)\) 的 优秀 做法：对于每一位相同的数字，我们可以把它加进一个相同的并查集中，然后就可以按照并查集的个数进行统计。例如，假设右 \(R\) 个并查集，那么：
\]
这是因为，每一位上的数字都可在 \([0,9]\) 这个区间的十个数中选择，而不能有前导零。
再考虑倍增优化。我们可以把每个区间按照二进制拆分，倍增处理，把每一块加入同一个并查集中。统计答案时先下传并查集到底（有点像线段树的 \(pushdown\) 操作），最后再对每个长度为 \(2^0=1\) 的区间进行答案统计，得到最终答案，总时间复杂度为 \(O(m \times n \log ^2n)\) 。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P=1e9+7;
LL n,m,ans,fa[20][100005];
bool flag;
inline LL read()
{
LL re=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
inline LL fd(LL x,LL y)
{
LL r=x;
while(fa[y][r]!=r) r=fa[y][r];
LL i=x,j;
while(i!=r) j=fa[y][i],fa[y][i]=r,i=j;
return r;
}
inline void merge(LL x,LL y,LL z)
{
LL fx=fd(x,z),fy=fd(y,z);
if(fx!=fy) fa[z][fx]=fa[z][fy];
}
int main()
{
n=read(),m=read();
for(LL i=0;i<=17;i++)
for(LL j=1;j<=n;j++)
fa[i][j]=j;
while(m--)
{
LL l1=read(),r1=read(),l2=read(),r2=read();
for(LL i=17;i>=0;i--)
if(l1+(1<<i)-1<=r1)
{
merge(l1,l2,i);
l1+=(1<<i),l2+=(1<<i);
}
}
for(LL i=17;i;i--)
for(LL j=1;j+(1<<i)-1<=n;j++)
{
merge(j,fd(j,i),i-1);
merge(j+(1<<(i-1)),fa[i][j]+(1<<(i-1)),i-1);
}
for(LL i=1;i<=n;i++) if(fd(i,0)==i) ans=flag?ans*10%P:9,flag=true;
printf("%lld",ans);
return 0;
}