3238: [Ahoi2013]差异

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 2512  Solved: 1140

[][][]

Description

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

---

 

后缀数组看这里 http://www.cnblogs.com/candy99/p/6250732.html

 

反串建SAM然后Parent Tree就是后缀树了

后缀树上两点的LCP就是LCA啊

然后树形DP，没必要显示建树，直接基数排序倒推行了

状态u作为LCA的时候，就是u的不同子树v的|Right|两两相乘的和

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=1e6+5;typedef long long ll;int n,d[N];char s[N];struct State{    int ch[26],par,val;}t[N];int sz,root,last;inline int nw(int _){t[++sz].val=_;return sz;}inline void iniSAM(){sz=0;root=last=nw(0);}void extend(int c){    int p=last,np=nw(t[p].val+1); d[np]=1;    for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;    if(!p) t[np].par=root;    else{        int q=t[p].ch[c];        if(t[q].val==t[p].val+1) t[np].par=q;        else{            int nq=nw(t[p].val+1);            memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));            t[nq].par=t[q].par;            t[q].par=t[np].par=nq;            for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;        }    }    last=np;}int c[N],a[N];void RadixSort(){    for(int i=1;i<=sz;i++) c[t[i].val]++;    for(int i=1;i<=n;i++) c[i]+=c[i-1];    for(int i=sz;i>=1;i--) a[c[t[i].val]--]=i; }ll dp(){    ll _=0;    for(int i=sz;i>=1;i--){        int v=a[i],u=t[v].par;        _+=(ll)t[u].val*d[u]*d[v];        d[u]+=d[v];    }    return _;}void solve(){     ll ans=(ll)n*(n+1)*(n-1)/2;    iniSAM();    for(int i=1;i<=n;i++) extend(s[i]-'a');    RadixSort();    printf("%lld",ans-2*dp());}int main(int argc, const char * argv[]) {    freopen("in","r",stdin);    scanf("%s",s+1);    n=strlen(s+1);    reverse(s+1,s+1+n);    solve();    return 0;}