题意：
给出一个数字串，问所有本质不同的子串的最大值之和
如果没有本质不同的要求，就是用单调栈求出每个数字前后第一个大于它的位置，扫一遍计算即可
现在要本质不同，用后缀数组
按字典序依次计算每个后缀的贡献
对于已经按字典序从小到大排好序的后缀i-1和i来说
以i为子串左端点，[i,height[i]]之间的为子串右端点 的子串已经在以i-1位左端点的字串中统计过了
所以对于每一个后缀i，新增的是以i为左端点，以[i+height[i],n]为右端点的子串的答案
每个后缀的答案分为两部分
设区间[i,i+height[i]-1]之间最大的是第j个数，第j个数后面第一个更大的是第k个数
第一部分为以i为左端点，以[k,n]之间的为右端点的答案
它的答案等同于以k为左端点，以[k,n]之间的为右端点的答案
这可以提前对每一个k都求出来
求法：
假设第i个数后面第一个更大的是第nxt个数，那么以i为左端点的贡献就是（nxt-i）* 第i个数
从右往左扫一遍，可以求出i为左端点，以[i,n]之间的为右端点的答案
第二部分为以i为左端点，以[i+height[i],k-1]为右端点的子串答案
这一共有k-1-(i+height[i])个区间，他们的最大值都是第j个数
找这个j的方法有很多
可以根据nxt倍增
求nxt可以用单调栈
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 200002 #define M 1000002 typedef long long LL; int n,k,mx,a[N],v[M],p,q,sa[2][N],rk[2][N],h[N]; int st[N],top; int nxt[N][20],qp,bit[20]; LL sum[N]; void mul(int *sa,int *rk,int *SA,int *RK) { for(int i=1;i<=n;i++) v[rk[sa[i]]]=i; for(int i=n;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k; for(int i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i; for(int i=1;i<=n;i++) RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]); } void presa() { p=0; q=1; qp=0; for(int i=0;i<=mx;++i) v[i]=0; for(int i=1;i<=n;i++) v[a[i]]++; for(int i=1;i<=mx;i++) v[i]+=v[i-1]; for(int i=1;i<=n;i++) sa[p][v[a[i]]--]=i; for(int i=1;i<=n;i++) rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]); for(k=1;k<n;k<<=1,swap(p,q),++qp) mul(sa[p],rk[p],sa[q],rk[q]); for(int i=1,kk=0;i<=n;i++) { int j=sa[p][rk[p][i]-1]; while(a[i+kk]==a[j+kk]) kk++; h[rk[p][i]]=kk; if(kk) kk--; } } void solve() { st[top=1]=n+1; for(int i=n;i;--i) { while(top && a[i]>=a[st[top]]) top--; nxt[i][0]=st[top]; st[++top]=i; } nxt[n+1][0]=n+1; for(int i=1;i<=qp;++i) for(int j=1;j<=n+1;++j) nxt[j][i]=nxt[nxt[j][i-1]][i-1]; for(int i=1;i<=n;++i) sum[i]=1ll*(nxt[i][0]-i)*a[i]; for(int i=n;i;--i) if(nxt[i][0]<=n) sum[i]+=sum[nxt[i][0]]; LL ans=sum[sa[p][1]]; int s,pos,now,to; for(int i=2;i<=n;++i) { s=sa[p][i]+h[i]; now=sa[p][i]; for(int j=qp;j>=0;--j) if(nxt[now][j]<s) now=nxt[now][j]; to=nxt[now][0]; if(to<=n) ans+=sum[to]; ans+=1ll*(to-s)*a[now]; } printf("%lld\n",ans); } int main() { int T; scanf("%d",&T); bit[0]=1; for(int i=1;i<=19;++i) bit[i]=bit[i-1]<<1; while(T--) { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&a[i]); mx=max(mx,a[i]); } a[n+1]=2e6; presa(); //for(int i=1;i<=n;i++) printf("%d ",sa[p][i]);puts(""); //for(int i=2;i<=n;i++) printf("%d ",h[i]); solve(); } }
ICPC2018焦作站 H. Can You Solve the Harder Problem?
原文：https://www.cnblogs.com/TheRoadToTheGold/p/14037568.html