自动搬运

查看原文

来自洛谷，原作者为

	lzqy_ 生而绚烂，璀璨如花。

搬运于2025-08-24 22:12:00，当前版本为作者最后更新于2023-12-30 15:01:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每个子串出现的时间都是一段区间，考虑线段树分治。

线段树的每个节点动态维护当前 $\text{LCP}$ 对应的子串，每次加入新串时更新。

那么瓶颈变为求任意两个子串的 $\text{LCP}$。

先把所有串接在一起建反串 SAM。

一个观察是任意子串 $\text{LCP}$ 可以看作两端后缀的 $\text{LCP}$ 对子串长度取 $\min$。因此，预处理出每段后缀在反串 SAM 上的位置，然后用 $O(n\log n)-O(1)$ LCA 即可做到 $O(n\log n)$ 的总复杂度。

但是本题过于卡空间，要把欧拉序求 LCA 换成树剖求 LCA。虽然变成了 $O(n\log ^2 n)$ 但其实比原先快了三分之一。

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int maxn=2000010;
const int MAXN=4000010;
il int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
struct edge{
	int v,to;
}e[maxn<<1];
int head[maxn],ecnt;
void addedge(int u,int v){
	e[++ecnt].v=v,e[ecnt].to=head[u],head[u]=ecnt;
}
struct sam{
	int ch[26],fa,len;
}a[maxn];
int loc[maxn],cnt=1,End=1;
void Insert(int c){
	int t=End,x=End=++cnt,nt=0,nx; a[x].len=a[t].len+1;
	loc[a[x].len]=x;//////////////////
	for(;t&&!nt;t=a[t].fa,nt=a[t].ch[c]) a[t].ch[c]=x;
	if(!t){a[x].fa=1;return ;}
	if(a[t].len+1==a[nt].len){a[x].fa=nt;return ;}
	nx=++cnt,a[nx].len=a[t].len+1;
	a[nx].fa=a[nt].fa,a[nt].fa=a[x].fa=nx;
	for(int i=0;i<26;i++) a[nx].ch[i]=a[nt].ch[i];
	for(;a[t].ch[c]==nt;t=a[t].fa) a[t].ch[c]=nx;
}
struct str{
	int l,r,tl,tr;
}A[maxn];
int sz[maxn],zson[maxn],dep[maxn],fa[maxn];
int dfn[maxn],DFN[maxn],top[maxn],idx;
void dfs1(int fath,int x){
//	printf("!!!%d\n",x);
	dep[x]=dep[fath]+1,fa[x]=fath;
	for(int i=head[x];i;i=e[i].to)
		if(e[i].v^fath){
			dfs1(x,e[i].v),sz[x]+=sz[e[i].v];
			if(sz[zson[x]]<sz[e[i].v]) zson[x]=e[i].v;
		}sz[x]++; 
}
void dfs2(int x){
	dfn[x]=++idx,DFN[idx]=x;
	if(zson[fa[x]]^x) top[x]=x;
	else top[x]=top[fa[x]];
	if(zson[x]) dfs2(zson[x]);
	for(int i=head[x];i;i=e[i].to)
		if(e[i].v!=fa[x]&&e[i].v!=zson[x]) dfs2(e[i].v);
}
int dl[MAXN],dr[MAXN];
int n,m,q,L[maxn],R[maxn];
char c[maxn],C[maxn];
int lca(int x,int y){
	while(top[x]^top[y])
		dfn[top[x]]>dfn[top[y]]?x=fa[top[x]]:y=fa[top[y]];
	return dfn[x]>dfn[y]?y:x;
}
int lcp(int i,int j){
	return a[lca(loc[n-i+1],loc[n-j+1])].len;
}
void Add(int i,int l,int r,int L,int R,int sl,int sr){
	if(l>=L&&r<=R){
		if(dl[i]&&dr[i]) dr[i]=dl[i]+min(lcp(dl[i],sl),min(dr[i]-dl[i]+1,sr-sl+1))-1;
		else dl[i]=sl,dr[i]=sr;
		return ;
	}int mid=l+r>>1;
	if(mid>=L) Add(i<<1,l,mid,L,R,sl,sr);
	if(mid<R) Add(i<<1|1,mid+1,r,L,R,sl,sr);
}
void Print(int i,int l,int r,int sl,int sr){
	if(dl[i]&&dr[i]){
		if(sl&&sr) sr=sl+min(lcp(dl[i],sl),min(dr[i]-dl[i]+1,sr-sl+1))-1;
		else sl=dl[i],sr=dr[i];
	}
	if(l==r){
		printf("%d\n",(sl&&sr)?sr-sl+1:0);
		return ;
	}int mid=l+r>>1;
	Print(i<<1,l,mid,sl,sr);
	Print(i<<1|1,mid+1,r,sl,sr);
}
int main(){
	m=read();
	for(int i=1;i<=m;i++){
		scanf("%s",C+1);
		L[i]=R[i-1]+1,R[i]=L[i]+strlen(C+1)-1;
		for(int j=L[i];j<=R[i];j++) c[j]=C[j-L[i]+1];
	}n=strlen(c+1);
	for(int i=n;i;i--) Insert(c[i]-'a');
	for(int i=2;i<=cnt;i++)
		addedge(a[i].fa,i),addedge(i,a[i].fa);
	dfs1(0,1),dfs2(1);
	q=read();
	for(int i=1;i<=q;i++){
		int op=read(),x=read();
		if(op==1){
			A[i].l=L[x]+read()-1;
			A[i].r=L[x]+read()-1;
			A[i].tl=i;
		}
		else A[x].tr=i-1;
	}
	for(int i=1;i<=q;i++)
		if(!A[i].tr) A[i].tr=q;
	for(int i=1;i<=q;i++)
		if(A[i].l) Add(1,1,q,A[i].tl,A[i].tr,A[i].l,A[i].r);
	Print(1,1,q,0,0);
	return 0;
}