• 题解：

  • 分成两部分来求，$\sum (len(T_{i})+len(T_{j}))$显然是：$\frac{(N-1)N(N+1)}{2}$
  • 另外一部分即所有后缀的$lcp$之和的二倍，枚举每一个$sa[i]$；
  • 这样对于每个j从小到大的$sa[j](j<i)$来说和$sa[i]$的$lcp$是连续的且单调递增，这取决于$j+1$到$i$的$height$最小值；
  • 求出$sa$和$ht$后，用一个单调上升的队列维护每一段的答案；
    1 #include
              
                2 #define ll long long 3 #define rg register 4 using namespace std; 5 const int N=500010; 6 int len,c[N],x[N],y[N],sa[N],top,st[N],rk[N],ht[N]; 7 ll ans,sum[N]; 8 char s[N];  9 void build_sa(int n,int m){10     for(rg int i=0;i
               
                =k)y[p++]=sa[i]-k;17         for(rg int i=0;i
                
                 =ht[i])top--;50         st[++top]=i;51         sum[top] = sum[top-1] + 2ll * (st[top] - st[top-1]) * ht[i];52         ans -= sum[top];53     }54     printf("%lld\n",ans);55     return 0;56 }
                
               
              

     

  • upd:20190106  学会了$SAM$的解法
  • 还是考虑$\sum lcp(i,j)$  (下文的$len$指节点$right$集合的最大长度，$sum$为节点的$parent$子树里的后缀个数)
  • 后缀树和$parent$树的联系：
    • 在$parent$树上前缀的最长后缀是在他们对应节点的$lca$的$len$；
    • 那么我们将串反过来建$SAM$的话$parent$树可以回答后缀间的$lcp$了；
  • 节点$u$作为$lca$的次数$*2$是：$sum_{u}  (sum_{u} - 1)  -  \sum_{v} sum_{v} (sum_{v}-1)$ 
  • 整理一下每个点贡献为：$sum_{u}(sum_{u}-1) * (len[u] - len[pa[u]]) $
  • 另一种的理解：

  • $\sum lcp(i,j)  = \sum_{子串x}  * \sum_{i} \sum_{j} [x是后缀i,j的公共前缀] $

  • 每个节点的不同子串个数为$len[u]-len[pa[u]]$立即推出式子；
  • 其实仔细想想对这个题不翻转答案也是一样的QAQ；
  • 1 #include
              
                2 #define ll long long 3 using namespace std; 4 const int N=1000010; 5 int n,lst,ch[N][26],cnt,len[N],pa[N],w[N],a[N],v[N]; 6 char s[N]; 7 inline void ins(int c){ 8     int p=lst,np;  9     len[lst=np=++cnt]=len[p]+1;10     v[np]=1;11     while(p&&!ch[p][c])ch[p][c]=np,p=pa[p];12     if(!p)pa[np]=1;13     else {14         int q=ch[p][c];15         if(len[q]==len[p]+1)pa[np]=q;16         else{17             int nq=++cnt;18             len[nq]=len[p]+1;19             memcpy(ch[nq],ch[q],sizeof(ch[q]));20             pa[nq]=pa[q];pa[q]=pa[np]=nq;21             while(p&&ch[p][c]==q)ch[p][c]=nq,p=pa[p];22         }23     }24 }25 int main(){26     #ifndef ONLINE_JUDGE 27     freopen("bzoj3238.in","r",stdin);28     freopen("bzoj3238.out","w",stdout);29     #endif30     scanf("%s",s);31     lst=cnt=1;32     n=strlen(s);33     for(int i=0;i
               
                1;i--){39         int u=a[i];40         v[pa[u]]+=v[u];41         ans -= (ll)(len[u]-len[pa[u]])*v[u]*(v[u]-1);42     }43     cout << ans << endl;44     return 0;45 }