自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:07:47，当前版本为作者最后更新于2021-08-25 11:22:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先计算长度为 $1$ 的贡献即为 $\dfrac{n(n-1)}{2}$。

然后将数组差分，然后离散化。

所求变为求有多少对相同的子串，满足间隔至少为 $1$。

也就是求 $\sum_{i<j}\min(lcp(i,j),j-i-1)$。

$\sum_{i<j}lcp(i,j)$ 可以用后缀数组 + 单调栈/并查集求出，见 P4248 [AHOI2013]差异。

现在只需要减去多算的部分，就是对于所有 $lcp(i,j)>j-i-1$ 的 $(i,j)$，求出 $\sum lcp(i,j)-(j-i-1)$。

枚举 $len=j-i$，则需要减去所有 $lcp(i,j)\geq len$ 的 $(i,j)$ 多算的部分。

考虑 P1117 [NOI2016] 优秀的拆分 一题中设置关键点的做法，将所有编号为 $len$ 的倍数的点作为关键点。

对于关键点 $k$ 和 $k+len$，统计 $i\in[k-len+1,k]$ 的答案。

这样统计不到 $i$ 在倒数第二个关键点以后的答案，不过容易发现这些位置的 lcp 一定小于 $len$。

求出 $s=lcs(k,k+len)$，则只有 $i\in[k-\min(len,s)+1,k]$ 的部分需要统计，$k+len\leq i<k-s+1$ 时 lcp 一定小于 $len$。

再求出 $lcp(k,k+len)$，发现所求是一个等差数列求和，这道题就做完了。

时空复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+3;
unordered_map<int,int>mp;
int n,lg[N],s[N];
long long ans,w;
struct SA{
int u[N],v[N],sa[N],t[N],st[23][N],*rk=u,*b=v;
void in(){
	int i,j,x,y,m=n,k=0;
	for(i=1;i<=n;++i)++t[s[i]];
	for(i=1;i<=m;++i)t[i]+=t[i-1];
	for(i=n;i;--i)sa[t[rk[i]=s[i]]--]=i;
	for(i=1;k<n;i*=2,m=k){
		for(j=n-i+1,k=0,memset(t,0,m*4+4);j<=n;++j)b[++k]=j;
		for(j=1;j<=n;++j)if(++t[rk[j]],sa[j]>i)b[++k]=sa[j]-i;
		for(j=1;j<=m;++j)t[j]+=t[j-1];
		for(j=n;j;--j)sa[t[rk[b[j]]]--]=b[j];
		for(j=1,k=y=0,swap(rk,b);j<=n;++j,y=x)x=sa[j],rk[x]=b[x]==b[y]&&b[x+i]==b[y+i]?k:++k;
	}
	for(i=1,k=s[n+1]=0;i<=n;st[0][rk[i++]]=k)if(rk[i]>1)for(j=sa[rk[i]-1],k=max(k-1,0);s[i+k]==s[j+k];++k);
	for(i=0;i<20;++i)for(j=2,k=n-(1<<i+1)+2;j<k;++j)st[i+1][j]=min(st[i][j],st[i][j+(1<<i)]);
}
int lcp(int x,int y){
	if(x=rk[x],y=rk[y],x>y)swap(x,y);
	int i=lg[y-x];
	return min(st[i][x+1],st[i][y-(1<<i)+1]);
}
void ddz(){//单调栈
	b[0]=1,st[0][1]=0;
	for(int*h=st[0],*st=b,tp=0,i=2,j;i<=n;++i){
		for(;h[i]<h[j=st[tp]];--tp)w-=(j-st[tp-1])*1ll*h[st[tp]];
		st[++tp]=i,w+=(i-j)*1ll*h[i],ans+=w;
	}
}
}A,B;
void calc(int s,int p,int l){//等差数列求和
	int x=min(s,l)+p-1,y=max(p,l);
	if(x>=y)ans-=(x-y+1ll)*(x+y-2*l+2)/2;
}
int main(){
	int l,i,j=0;
	for(scanf("%d",&n),lg[0]=-1,ans=n*(n-1ll)/2,i=1;i<=n;++i)scanf("%d",s+i),lg[i]=lg[i>>1]+1;
	for(i=1,--n;i<=n;s[i]=mp[s[i]],++i)if(s[i]-=s[i+1],!mp[s[i]])mp[s[i]]=++j;//差分离散化
	A.in(),A.ddz(),reverse(s+1,s+n+1),B.in();
	for(l=1;l<=n;++l)for(j=l*2;j<=n;j+=l)i=j-l,calc(B.lcp(n-i+1,n-j+1),A.lcp(i,j),l);
	cout<<ans;
	return 0;
}