Description

Input

一行，一个字符串S

Output

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

Sample Input

cacao

Sample Output

HINT

2<=N<=500000,S由小写英文字母组成

题解

知识点：

后缀数组，单调栈，LCP

分析：

先推一推式子，看看有没有机会化简：

$$
\begin{aligned}
ans&=\displaystyle\sum_{1\leq i<j\leq n}len(T_{i})+len(T_{j})-2\times lcp(T_{i},T_{j})
\&=(\displaystyle\sum_{i=1}^{n-1}{\displaystyle\sum_{j=i+1}^{n}{i+j}})-(\displaystyle\sum_{1\leq i<j\leq n}2\times lcp(T_{i},T_{j}))
\&=((n-1)\times\displaystyle\sum_{i=1}^n{i})-(\displaystyle\sum_{1\leq i<j\leq n}2\times lcp(T_{i},T_{j}))
\&=\frac{(n-1)\times n\times (n+1)}{2}-\displaystyle\sum_{1\leq i<j\leq n}2\times lcp(T_{i},T_{j})
\end{aligned}
$$
我们可以发现式子的前半部分经过推算是一个常数项，非常容易处理，所以我们只用关注后半部分的内容即可。

后面的式子意义其实是所有的后缀两两组合的LCP。假如我们正着求解这个内容，时间复杂度是$O(n^2)$的，会超时。考虑反着计算，求两两之间的LCP，不如求每个LCP对答案的贡献有多少（因为其实LCP的值会重复出现很多次，所以这样计算非常高效）。通过性质可以知道，LCP（i，j）是等于他们之间的height值的最小值。可以通过这个性质，考虑维护一个线性的数据结构，算出每个height值最多向左和向右延伸多长（延伸的范围就是它的贡献区间，它在那一段上面都是最小值，LCP必定是它）。

那么我们现在着手思考如何快速求出左右延伸的最长距离。经查阅大体有两种不同的方法。然而我当时自己只想出了方法一（相对好理解）。

方法一：用一个单调栈维护向左最多能够走多远（遇到相等的可以先留下来，最后处理），这个栈是从栈底到栈顶非严格单调递增的，记录每个点的$l[i]$。同理，对向右最多能够走多远也同样地维护一次，记录下$r[i]$。最后每个点算上从$l[i]$到$i$和从$r[i]$到$i$一共有多少个贡献区间。由乘法原理可以知道，区间的个数应该是$(i-l[i]+1)\times(r[i]-i+1)$。这个就是每个位置的答案。累加起来就完成了，这里的时间复杂度是$O(n)$，常数也很小。

方法二：同样地用单调栈维护从左往右的最小值，然后在里面DP，DP记录往左数第一个小于等于当前位置height值的位置到现在这一位的贡献是多少，把贡献累加，计算答案。这里的时间复杂度也是$O(n)$，但是常数比方法一要大。

综上所述，总的来说就是先推完式子，把前一半变成一个常数，把后一半用后缀数组求出来，单调栈维护每个height值对所有区间的贡献。总体时间复杂度是$O(n\log_{2}n)$。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=500010;
int n,m=122,sa[maxn],rnk[maxn],height[maxn],y[maxn],c[maxn],pos,st[maxn],l[maxn],r[maxn];
long long ans,f[maxn];
char s[maxn];

void srt()
{
    int i;
    memset(c,0,sizeof(c));
    for (i=1;i<=n;i++)
        c[rnk[i]]++;
    for (i=2;i<=m;i++)
        c[i]+=c[i-1];
    for (i=n;i>=1;i--)
        sa[c[rnk[y[i]]]--]=y[i];
}

void getsa()
{
    int i,p=0,k;
    for (i=1;i<=n;i++)
    {
        rnk[i]=s[i]-96;
        y[i]=i;
    }
    srt();
    for (k=1;p<n;m=p,k<<=1)
    {
        p=0;
        for (i=n-k+1;i<=n;i++)
            y[++p]=i;
        for (i=1;i<=n;i++)
            if (sa[i]>k)
                y[++p]=sa[i]-k;
        srt();
        swap(rnk,y);
        rnk[sa[1]]=p=1;
        for (i=2;i<=n;i++)
            rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
    }
}

void getheight()
{
    int i,j,k=0;
    for (i=1;i<=n;i++)
    {
        if (k)
            k--;
        j=sa[rnk[i]-1];
        while (s[i+k]==s[j+k])
            k++;
        height[rnk[i]]=k;
    }
}

void solve1()
{
    int i;
    pos=0;
    st[pos]=0;
    height[st[pos]]=-(n+10);//预处理栈底
    for (i=1;i<=n;i++)
    {
        while (height[i]<height[st[pos]])
            pos--;
        if (st[pos]==0)
            l[i]=1;
        else
            l[i]=st[pos]+1;
        st[++pos]=i;
    }
    pos=0;
    st[pos]=n+1;
    height[st[pos]]=-(n+10);//同L67
    for (i=n;i>=1;i--)
    {
        while (height[i]<=height[st[pos]])
            pos--;
        if (st[pos]==n+1)
            r[i]=n;
        else
            r[i]=st[pos]-1;
        st[++pos]=i;
    }
    ans=1ll*(n-1)*n*(n+1)/2;
    for (i=1;i<=n;i++)
        ans-=2ll*(i-l[i]+1)*(r[i]-i+1)*height[i];
}

void solve2()
{
    int i,j;
    height[n+1]=0;
    for (i=1;i<=n;i++)
    {
        while (height[i]<height[st[pos]])
            pos--;
        j=st[pos];
        f[i]=f[j]+(i-j)*height[i];//DP
        ans-=2ll*f[i];
        st[++pos]=i;
    }
    ans+=1ll*(n-1)*n*(n+1)/2;
}

int main()
{
    int i,j;
    scanf("%s",s+1);
    n=strlen(s+1);
    getsa();
    getheight();
    solve1();
//	solve2();
    printf("%lld\n",ans);
    return 0;
}

通过这道题，我们可以看出一般的后缀数组的题目，都可以巧妙地利用单调栈和height数组的性质来解决问题（特别是对于字符串的LCP最大最小这类问题，而且明显模拟地去求会TLE的时候，可以考虑反着求贡献）。

正所谓正难则反！