P5161 WD与数列（后缀数组+单调栈+设置关键点）
panyf
·
·
题解
首先计算长度为 1 的贡献即为 \dfrac{n(n-1)}{2}。
然后将数组差分，然后离散化。
所求变为求有多少对相同的子串，满足间隔至少为 1。
也就是求 \sum_{i<j}\min(lcp(i,j),j-i-1)。
现在只需要减去多算的部分，就是对于所有 $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] 优秀的拆分](https://www.luogu.com.cn/problem/P1117) 一题中设置关键点的做法，将所有编号为 $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)$。
```cpp
#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;
}
```