bzoj3238 [Ahoi2013]差异-白红宇

bzoj3238 [Ahoi2013]差异

阅读量：4646 次

发布时间：2019-06-09

本文共 2205 字，大约阅读时间需要 7 分钟。

后缀自动机秒题。

首先观察公式，发现它最难的地方在求所有后缀的LCP之和。

首先回想一下求两个后缀的LCP怎么搞？

先翻转原串，然后在fail树上找到它们的LCA，LCA节点的step值即为它们的最长公共前缀。

延续这个思路，将问题转化成，给定一颗树，每个节点上有一个权值，现在有很多特殊点，一对特殊点的权值为它们LCA的权值，求所有点对的权值和。

树形dp秒之。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 using namespace std;#define mem1(i,j) memset(i,j,sizeof(i))#define mem2(i,j) memcpy(i,j,sizeof(i))#define LL long long#define up(i,j,n) for(int i=(j);i<=(n);i++)#define FILE "dealing"#define poi vec#define eps 1e-10#define db double const int maxn=1010000,inf=1000000000,mod=1000000007;int read(){ int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0',ch=getchar();} return f*x;}bool cmax(int& a,int b){return a
                 
                  b?a=b,true:false;}struct SAM{ int pre[maxn],c[maxn][26],step[maxn],sa[maxn],cou[maxn],val[maxn],cnt,now,Len; SAM(){mem1(pre,0);mem1(c,0);mem1(step,0);cnt=now=1;} int extend(int x){ int np,nq,q,p; p=now;now=np=++cnt;step[np]=step[p]+1;val[np]++; while(p&&!c[p][x])c[p][x]=np,p=pre[p]; if(!p)pre[np]=1; else { q=c[p][x]; if(step[q]==step[p]+1)pre[np]=q; else { step[nq=++cnt]=step[p]+1; mem2(c[nq],c[q]); pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(p&&c[p][x]==q)c[p][x]=nq,p=pre[p]; } } } int getsort(){ up(i,1,cnt)cou[step[i]]++; up(i,1,cnt)cou[i]+=cou[i-1]; for(int i=cnt;i>=1;i--)sa[cou[step[i]]--]=i; } int walkprepare(){now=1,Len=0;} int walk(int x){ while(pre[now]&&!c[now][x])now=pre[now],Len=step[now]; if(!c[now][x])return 0; Len++;now=c[now][x];return Len; } int build(char* s){ int n=strlen(s+1); up(i,1,n)extend(s[i]-'a'); walkprepare(); getsort(); }}a;char s[maxn];int main(){// freopen(FILE".in","r",stdin);// freopen(FILE".out","w",stdout); scanf("%s",s+1);int n=strlen(s+1); reverse(s+1,s+n+1); a.build(s); LL ans=0; up(i,1,n)ans+=((LL)n-i+1)*(n-1); int *sa=a.sa,*len=a.step,*val=a.val,*pre=a.pre; for(int i=a.cnt;i>=1;i--){ ans-=2LL*len[pre[sa[i]]]*val[sa[i]]*val[pre[sa[i]]]; val[pre[sa[i]]]+=val[sa[i]]; } printf("%lld\n",ans); return 0;}