问了lcp了显然要后缀数组对吧
然后就变成了听说是HNOI2016 D2T1的简化版？单调栈处理出每个点向左右扩展的距离（贡献范围）即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// <3238.cpp> - 08/16/16 19:57:48 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=500010; const int INF=1e9; char s[MAXN]; int n; int sa[MAXN],rk[MAXN]; int v[MAXN],x[MAXN],y[MAXN]; int h[MAXN]; void go(){ int m=29; for(int i=1;i<=n;i++)v[x[i]=(s[i]-'a'+1)]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[i]]--]=i; for(int j=1;j<=n;j<<=1){ int p=0; for(int i=n-j+1;i<=n;i++)y[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j; for(int i=1;i<=m;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[y[i]]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[y[i]]]--]=y[i]; swap(x,y);x[sa[1]]=1; p=1; for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p; if(p==n)break;m=p; } } void calh(){ int k=0,j; for(int i=1;i<=n;i++)rk[sa[i]]=i; for(int i=1;i<=n;h[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++); } int st[MAXN],l[MAXN],r[MAXN]; int main(){ scanf("%s",s+1); n=strlen(s+1); go();calh(); int t=1;st[1]=1; for(int i=2;i<=n;i++){ while(t>1&&h[i]<h[st[t]])t--; l[i]=st[t]; st[++t]=i; } st[t=1]=n+1; for(int i=n;i>=2;i--){ while(t>1&&h[i]<=h[st[t]])t--; r[i]=st[t]; st[++t]=i; } lol ans=1ll*(n-1)*n*(n+1)>>1; for(int i=2;i<=n;i++)ans-=1ll*(i-l[i])*(r[i]-i)*h[i]<<1; printf("%lld",ans); return 0; } |
说点什么