Steven_Meng's Blog

首先考虑暴力的做法，不要把注意力放在字串上面，考虑$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_{l_1}==S_{l_2} \text{&&} S_{l_1 +1} == S_{l_2+1} \text{&&} \cdots \text{&&} S_{r_1}==S_{r_2}

于是考虑并查集，把$l_1,l_2$和$l_1+1,l_2+1 \cdots$$r_1,r_2$连边，发现一个连通块里面的数字必须是一样的，于是每个连通块里面数字有$10$种选择，但是包含$1$的那个连通块不能为$0$，只有$9$种选择，设连通块个数是$num$，答案就是$9 \times 10^{num-1}$

这样时间复杂度$O(n^2 \alpha(n))$，能够拿$30 pts$

#include <bits/stdc++.h>
#define MAXN 100005
#define MOD 1000000007
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
	int fa[MAXN];
	inline void Init(){
		for (register int i=0;i<MAXN;++i) fa[i]=i;
	}
	inline int Find(int x){
		return fa[x]==x?x:fa[x]=Find(fa[x]);
	}
}
using namespace BCJ;
int main(){
	int n=read(),m=read();
	Init();
	for (register int i=1;i<=m;++i){
		int l1=read(),r1=read(),l2=read(),r2=read();
		for (register int j=l1;j<=r1;++j){
			fa[Find(j)]=Find(j-l1+l2);
		}
	}
	int ans=0;
	for (register int i=1;i<=n;++i){
		if (fa[i]==i) ans++;
	}
	long long ret=9;
	for (register int i=1;i<=ans-1;++i) ret=(ret*10)%MOD;
	printf("%d\n",ret);
}

考虑如何优化，肯定是在刚才的并查集上面优化，不妨考虑以空间换时间，我们创建一个二维的并查集数组$f[][]$，其中$f[i][j]$代表$\forall p \in [0,2^i-1] , (j+p)和(f[i][j]+p)$之间都有边相连。

考虑如何连边，这个类似于二进制拆分。

for (register int j=LOG-1;j>=0;--j){
	int d=(1<<j);
	if (l1+d-1<=r1){
		Merge(l1,l2,j);
		l1+=d,l2+=d;
	}
}

比方说我们连边$[1,3],[5,7]$如下图：

连完边以后还没有结束，我们现在还不能知道有多少连通块，于是我们要层层下推。

具体来说<i , f[i]> \text{on } f[j] \Rightarrow <i , f[i]> \text{on } f[j-1] \text{ && } <i +2^{j-1}, f[i]+2^{j-1} > \text{on } f[j-1]

这个过程可以类比$\rm ST$表初始化：

ST[i][j]=max(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);

处理完之后，$f[0]$这一层就是我们要的并查集。

#include <bits/stdc++.h>
#define MAXN 100005
#define LOG 25
#define MOD 1000000007
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
	int f[LOG][MAXN];
	inline void Init(int n){
		for (register int i=1;i<=n;++i){
			for (register int j=0;j<LOG;++j){
				f[j][i]=i;
			}
		}
	}
	inline int Find(int *fa,int x){
		return fa[x]==x?x:fa[x]=Find(fa,fa[x]);
	}
	inline void Merge(int x,int y,int lev){
		int fax=Find(f[lev],x),fay=Find(f[lev],y);
		if (fax!=fay) f[lev][f[lev][fax]]=f[lev][fay];
	}
}
using namespace BCJ;
int main(){
	int n=read(),m=read();
	Init(n);
	for (register int i=1;i<=m;++i){
		int l1=read(),r1=read(),l2=read(),r2=read();
		for (register int j=LOG-1;j>=0;--j){
			int d=(1<<j);
			if (l1+d-1<=r1){
				Merge(l1,l2,j);
				l1+=d,l2+=d;
			}
		}
	}
	for (register int j=LOG-1;j>=1;--j){
		int d=(1<<j);
		for (register int i=1;i+d-1<=n;++i){
			int fa=Find(f[j],i);
			Merge(i,fa,j-1);
			Merge(i+(d>>1),fa+(d>>1),j-1);
		}
	}
	int ans=0;
	for (register int i=1;i<=n;++i) ans+=(Find(f[0],i)==i);
	long long ret=9;
	for (register int i=1;i<=ans-1;++i) ret=(ret*10)%MOD;
	printf("%d\n",ret);
}

总结：这道题将多次重复的加边操作通过倍增优化到$O(\log n)$级别，和线段树优化建图比较像，都是把多个重复的边压成一条，以优化时间/内存。