[BZOJ3238][AHOI2013]差异 [后缀数组+单调栈]

题目地址 - GO->

题目大意:

给定一个长度为 $n$ 的字符串 $S$ ,令 $T_{i}$ 表示它从第 $i$ 个字符开始的后缀，求以下这个式子的值:

\sum_{1 \leq i < j \leq n} l e n (T_{i}) + l e n (T_{j}) - 2 \times l c p (T_{i}, T_{j})

其中， $len (a)$ 表示字符串 $a$ 的长度， $lcp (a, b)$ (longest common prefix)表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

分析:

我们将式子变一下形，可以容易的得到:

[\sum_{1 \leq i < j \leq n} l e n (T_{i}) + l e n (T_{j})] - 2 \times [\sum_{1 \leq i < j \leq n} l c p (T_{i}, T_{j})]

因为前半部分是求后缀长度和，而后缀长度是递减的，所以可以由等差数列公式得到 $\sum_{1 \leq i \leq n} l e n (T_{i}) = \frac{n \times (n + 1)}{2}$ ，而在计算每一个 $l e n (T_{i})$ 时，它会被算 $n - 1$ 次，所以前半部分我们就 $O (1)$ 得到为

\sum_{1 \leq i < j \leq n} l e n (T_{i}) + l e n (T_{j}) = (n - 1) \times [\sum_{1 \leq i \leq n} l e n (T_{i})] = (n - 1) \times (\frac{n \times (n - 1)}{2})

那么对于后面的，一看数据范围 $2 \leq n \leq 500000$ ，总不能 $O (n^{2})$ 的计算吧。

所以这里运用了一个巧妙的方法，单调栈。

因为我们发现 $l c p$ 是按照 $s a$ (后缀数组)中的 $r a n k$ 单调的，而两个后缀之间的 $l c p$ 是 $h e i g h t$ 数组的区间最小值，所以查询两个后缀的 $l c p$ 可以用 $r m q$ 预处理,但是对于多个如何处理呢？

所以我们先对所有的下标按照 $r a n k$ 排个序，然后往单调栈里面加，单调栈维护的 $l c p$ 递增不减，每新加入一个 $l c p (T_{i - 1}, T_{i})$ 时，我们要计算 $T_{i}$ 对于答案的贡献，那么由于栈中的 $l c p$ 大小是单调递增不减的，所以当加入一个新的 $l c p$ 时，要把栈顶大于这个新的值的元素给删除，并且还要消除比它大的这些元素的影响，而一个新的 $l c p$ 的贡献等于之前 $l c p$ 比它小的贡献加上 $l c p$ 比它大的个数乘以它的 $l c p$ 大小，要消除的影响就是每个比它大的 $l c p \times$ 大的个数。所以我们可以用一个单调栈来完成这个操作。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=1e6+10;
int n,minv;
int stk[M],top;
char s[M];
int cnt[M],rak[M],y[M],sa[M],A,p,len,h[M],all[M];
ll ans,sumv,now;
void getsa(){
    len=strlen(s)+1;n=len-1;A=256;
    for(int i=0;i<len;i++) ++cnt[rak[i]=s[i]];
    for(int i=1;i<=A;i++) cnt[i]+=cnt[i-1];
    for(int i=len-1;i>=0;i--) sa[--cnt[rak[i]]]=i;
    for(int k=1;k<=len;k<<=1){
        for(int i=0;i<=A;i++) cnt[i]=0;p=0;
        for(int i=len-k;i<len;i++) y[p++]=i;
        for(int i=0;i<len;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(int i=0;i<len;i++) ++cnt[rak[y[i]]];
        for(int i=1;i<=A;i++) cnt[i]+=cnt[i-1];
        for(int i=len-1;i>=0;i--) sa[--cnt[rak[y[i]]]]=y[i];
        swap(rak,y);p=1;rak[sa[0]]=0;
        for(int i=1;i<len;i++){
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]){
                rak[sa[i]]=p-1;
            }else{
                rak[sa[i]]=p++;
            }
        }
        if(p>=len) break;A=p;
    }
    for(int i=1;i<=n;i++) rak[sa[i]]=i;
}
void geth(){
    int k=0;
    for(int i=0;i<n;i++){
        if(!rak[i]) continue;
        if(k)--k;
        int j=sa[rak[i]-1];
        for(;s[i+k]==s[j+k];k++);
        h[rak[i]]=k;
    }
    for(int i=n;i>=1;i--) ++sa[i],rak[i]=rak[i-1];
}
int rmq[M][22];
void initrmq(){
    for(int i=1;i<=n;i++) rmq[i][0]=h[i];
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;j++){
            rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
        }
    }
}
int lcp(int a,int b){
    if(a>n||b>n) return 0;
    if(a==b) return n-a+1;
    ++a;
    if(a>b)swap(a,b);
    int k=0;
    for(;(1<<(k+1))<=b-a+1;k++);
    return min(rmq[a][k],rmq[b-(1<<k)+1][k]);
}
int ls[M];
int main(){
    scanf("%s",s);
    getsa();
    geth();
    initrmq();
    for(int i=1;i<=n;i++) ls[i]=rak[i];
    sort(ls+1,ls+n+1);//按照rank排序
    for(int i=2;i<=n;i++){
        minv=lcp(ls[i-1],ls[i]);//rank相邻的两个lcp是比较大的，因为相似度比较高。
        now=0;
        while(top&&stk[top]>=minv){
            now+=all[top];//累计大的个数
            ans-=(1ll*all[top]*stk[top]);//减去大的影响
            --top;
        }
        stk[++top]=minv;all[top]=now+1;//当前的lcp=minv，个数=前面大的个数+自己。
        ans+=(1ll*stk[top]*all[top]);//加上当前的贡献
        sumv+=ans;//每次统计到答案里面
    }
    printf("%lld
",(1ll*n*(n+1))/2ll*(n-1)-2ll*sumv);
    return 0;
}

这个题，看其他人还有后缀树+虚树，后缀自动机等做法，下面有个相似的题目，也可以用这个方法:BZOJ3879 SVT

若有错，请大佬指出，Orz。