【BZOJ-3238】差异 后缀数组 + 单调栈

3238: [Ahoi2013]差异

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1561  Solved: 734
[Submit][Status][Discuss]

Description

Input

一行，一个字符串S

Output

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

Sample Input

cacao

Sample Output

54

HINT

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

Source

Solution

后缀数组+单调栈

LCP的话，预处理ST表，然后直接求?似乎不好,不过后缀数组的话很好想

肯定是对height做文章...总后缀的长度和很好求..随便一算就出来了...考虑LCP的问题

想法是枚举i,对于每个height[i]前后扩展,找出对答案的贡献,然后最后计算答案..似乎可以,但是WA掉了..

原因是有重复计算,那么要不重复..上述是左右两边扩展,使得区间[l,r]中height[i]为最小,重复的很多,思想还是一样的不过不妨把区间看成[l,r)(PS,其实表述不准确),这样的扩展下去,即向左有限制,向右无限制,向左扩展到相等的就停止,向右遇到相等的可以继续.

那么需要用单调栈去维护扩展的过程..这样就能得到每一个height[i]对答案的贡献了,最后答案需要减掉(i-L[i]+1)*(R[i]-i+1)*(height[i])

注意:

在计算答案的过程中要强制转换.(旧错不再犯)

处理后的单调栈内如果为空,说明可以扩展到开头/结尾(也是看别人的才反应过来的)

PS:正解好像不是这个?...不过POJ上好像做过类似的题,所以写起来还是比较快的..

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 500010
char S[maxn]; int SA[maxn],len;
int ws[maxn],wv[maxn],wa[maxn],wb[maxn];
int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void DA(char *r,int *sa,int n,int m)
{
    int p,*x=wa,*y=wb,*t;
    for (int i=; i<m; i++) ws[i]=;
    for (int i=; i<n; i++) ws[x[i]=r[i]]++;
    for (int i=; i<m; i++) ws[i]+=ws[i-];
    for (int i=n-; i>=; i--) sa[--ws[x[i]]]=i;
    p=; for (int j=; p<n; j*=,m=p)
        {
            p=; for (int i=n-j; i<n; i++) y[p++]=i;
            for (int i=; i<n; i++) if (sa[i]>=j) y[p++]=sa[i]-j;
            for (int i=; i<n; i++) wv[i]=x[y[i]];
            for (int i=; i<m; i++) ws[i]=;
            for (int i=; i<n; i++) ws[wv[i]]++;
            for (int i=; i<m; i++) ws[i]+=ws[i-];
            for (int i=n-; i>=; i--) sa[--ws[wv[i]]]=y[i];
            t=x; x=y; y=t; p=; x[sa[]]=;
            for (int i=; i<n; i++)
                x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
        }
}
int rank[maxn],height[maxn];
void calheight(char *r,int *sa,int n)
{
    int k=;
    for (int i=; i<=n; i++) rank[sa[i]]=i;
    for (int i=; i<n; height[rank[i++]]=k)
        {k?k--:;for (int j=sa[rank[i]-]; r[i+k]==r[j+k]; k++);}
}
int stack[maxn],top,L[maxn],R[maxn];
long long tot,lcp;
int main()
{
    scanf("%s",S); len=strlen(S); S[len]=;
    DA(S,SA,len+,);  calheight(S,SA,len);
    tot=(long long)((long long)len*(long long)(len-)*(long long)(len+)/);
    top=; stack[]=;
    for (int i=; i<=len; i++)
        {
            while (top && height[stack[top-]]>height[i]) top--;
            if (top) L[i]=stack[top-]+;
            else L[i]=;
            stack[top++]=i;
        }
    top=; stack[]=len;
    for (int i=len; i>=; i--)
        {
            while (top && height[stack[top-]]>=height[i]) top--;
            if (top) R[i]=stack[top-]-;
            else R[i]=len;
            stack[top++]=i;
        }
    for (int i=; i<=len; i++)
        lcp+=(long long)*(long long)(i-L[i]+)*(long long)(R[i]-i+)*(long long)height[i];
    printf("%lld\n",tot-lcp);
    return ;
}