自动搬运

查看原文

来自洛谷，原作者为

	Fuyuki 闲云遮月，清风袭花

搬运于2025-08-24 22:19:24，当前版本为作者最后更新于2020-04-05 18:23:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于每个本质不同的字符串 $T$，假设在前缀 $[1,r]$ 中最后一次出现的位置（右端点）为 $last_T$，那么当左端点取到 $[1,last_T-|T|+1]$ 这个区间内的时候，$T$ 会对答案产生 $1$ 的贡献。

采用扫描线的思路，对每个右端点维护所有左端点的答案。

如果把反串的后缀树建出来，那么将右端点右移一位到达 $r$ 就相当于将后缀树上一条到根的路径上的所有字符串的 $last$ 修改成 $r$。如果把这个看作 LCT 中的 access 操作，可以发现划分出来的每条链上的 $last$ 都相同，并且代表的字符串长度连续。

因此直接用 LCT 进行修改，将链合并的时候就是将一段长度连续的本质不同字符串的 $last$ 进行修改，这个对答案的影响可以表现成区间加一个公差为 $1$ 的等差数列，用线段树维护即可。

注意到 access 操作的次数是均摊 $O(logn)$，那么只会进行 $O(nlogn)$ 次线段树上的区间修改，复杂度是 $O(nlog^2n)$ 的。而线段树上查询一次的复杂度是 $O(logn)$，所以总复杂度是 $O(nlog^2n+mlogn)$。

我的实现中将区间加等差数列单点查询转化成区间加常数区间查询，用树状数组实现的时候感觉稍微好写一些。

#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define P pair<int,int>
#define ll long long int
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e5+1,INF=0x3f3f3f3f;
V cmin(int&x,int y){if(y-x>>31)x=y;}
namespace SAM{
	int ch[N][26],fa[N],len[N],tot=1,last=1;
	V cpy(int x,int y){FOR(i,0,25)ch[x][i]=ch[y][i];}
	I ins(int x){
		int p(last),np,q,nq;
		len[np=last=++tot]=len[p]+1;
		while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
		if(!p)return fa[np]=1,last;
		if(len[q=ch[p][x]]==len[p]+1)return fa[np]=q,last;
		cpy(nq=++tot,q),len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;
		while(p&&ch[p][x]==q)ch[p][x]=nq,p=fa[p];
		return last;
	}
}
namespace seg{
	ll c[N],d[N];
	I lowbit(int x){return x&-x;}
	V add(int x,int y){for(ll w=x*y;x<N;x+=lowbit(x))c[x]+=y,d[x]+=w;}
	ll ask(int x){
		ll out=0,tmp=0;
		for(int p=x;p;p^=lowbit(p))out+=c[p],tmp+=d[p];
		return out*(x+1)-tmp;
	}
	ll ask(int l,int r){return ask(r)-ask(l-1);}
	V add(int l,int r,int x){add(l,x),add(r+1,-x);}
}
namespace LCT{
	int fa[N],ch[N][2],last[N],tag[N],len[N],val[N];
	I id(int x){return x==ch[fa[x]][1];}
	I nrt(int x){return x==ch[fa[x]][id(x)];}
	V upd(int x){val[x]=len[x];FOR(i,0,1)cmin(val[x],val[ch[x][i]]);}
	V rot(int x){
		int y=fa[x],z=fa[y],p=id(x),w=ch[x][p^1];
		if(nrt(y))ch[z][id(y)]=x;if(w)fa[w]=y;
		fa[y]=x,fa[x]=z,ch[x][p^1]=y,ch[y][p]=w,upd(y),upd(x);
	}
	V add(int x,int w){last[x]=tag[x]=w;}
	V psd(int x){if(tag[x])FOR(i,0,1)add(ch[x][i],tag[x]);tag[x]=0;}
	V psa(int x){if(nrt(x))psa(fa[x]);psd(x);}
	V spl(int x){
		for(psa(x);nrt(x);rot(x))if(nrt(fa[x]))
			rot(id(x)==id(fa[x])?fa[x]:x);
	}
	V acc(int x,int now){
		for(int p=x,y=0;p;p=fa[y=p]){
			spl(p),ch[p][1]=y,upd(p);
			if(last[p])seg::add(last[p]-SAM::len[p]+1,last[p]-val[p]+1,-1);
		}
		spl(x),add(x,now),seg::add(now-SAM::len[x]+1,now,1);
	}
	V init(){
		val[0]=INF;
		FOR(i,1,SAM::tot){
			val[i]=len[i]=SAM::len[fa[i]=SAM::fa[i]]+1;
			tag[i]=ch[i][0]=ch[i][1]=last[i]=0;
		}
	}
}
char a[N];
ll ans[N];
vector<P>q[N];
int T,n,m,l,r,pos[N];
int main(){
	scanf("%s%d",a+1,&m),n=strlen(a+1);
	FOR(i,1,m)scanf("%d%d",&l,&r),q[r].push_back(P(i,l));
	FOR(i,1,n)pos[i]=SAM::ins(a[i]-'a');
	LCT::init();
	FOR(i,1,n){
		LCT::acc(pos[i],i);
		for(P x:q[i])ans[x.first]=seg::ask(x.second,i);
	}
	FOR(i,1,m)cout<<ans[i]<<'\n';
	return 0;
}