3238: [Ahoi2013]差异
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 2527 Solved: 1146
[Submit][Status][Discuss]
Description
Input
一行,一个字符串S
Output
一行,一个整数,表示所求值
Sample Input
cacao
Sample Output
54
HINT
2<=N<=500000,S由小写英文字母组成
Source
后缀数组,好像正解是sam,反正我不会
很明显前两项是可以O(1)算出来的=(n-1)*(n+1)*n/2
后一项可以用烂大街的rmq+lcp做。
lcp(i,j)=i->j中间最小的lcp*i->j在lcp数组中的距离。
也就是说对于一个lcp,他对答案的贡献是l->r且min(lcp[l->r)=lcp[i] i:[l->r] 那么我们就可以用单调栈
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define N 500010 int n,k; char s[N]; int rank[N],sa[N],temp[N],lcp[N],st[N],l[N],r[N]; inline bool cp(int i,int j) { if(rank[i]!=rank[j]) return rank[i]<rank[j]; int ri=i+k<=n?rank[i+k]:-1; int rj=j+k<=n?rank[j+k]:-1; return ri<rj; } void Sa() { for(int i=1;i<=n;++i) { rank[i]=s[i]; sa[i]=i; } for(k=1;k<=n;k<<=1) { sort(sa+1,sa+n+1,cp); temp[sa[1]]=1; for(int i=2;i<=n;++i) temp[sa[i]]=temp[sa[i-1]]+(cp(sa[i-1],sa[i])); for(int i=1;i<=n;++i) rank[i]=temp[i]; } } void Lcp() { for(int i=1;i<=n;++i) rank[sa[i]]=i; int h=0; for(int i=1;i<=n;++i) { if(rank[i]<=1) continue; int j=sa[rank[i]-1]; if(h>0) --h; for(;i+h<=n&&j+h<=n;++h) if(s[i+h]!=s[j+h]) break; lcp[rank[i]-1]=h; l[rank[i]-1]=r[rank[i]-1]=rank[i]-1; } } void solve() { n=strlen(s+1); Sa(); Lcp(); int top=0; for(int i=1;i<n;++i) { while(top&&lcp[i]<=lcp[st[top]]) r[st[top-1]]=r[st[top]],l[i]=l[st[top--]]; st[++top]=i; } while(top) r[st[top-1]]=r[st[top--]]; ll ans=(ll)n*(ll)(n-1)*(ll)(n+1)>>1; for(int i=1;i<n;++i) ans-=2*(ll)(r[i]-i+1)*(ll)(i-l[i]+1)*(ll)lcp[i]; printf("%lld ",ans); } int main() { scanf("%s",s+1); solve(); return 0; }