3238: [Ahoi2013]差异

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 1561  Solved: 734

[][][]

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
     
      #include
      
       #include
       
        using namespace std;#define maxn 500010char 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=0; i
        
         =0; i--) sa[--ws[x[i]]]=i;    p=1; for (int j=1; p
         
          =j) y[p++]=sa[i]-j;            for (int i=0; i
          
           =0; i--) sa[--ws[wv[i]]]=y[i]; t=x; x=y; y=t; p=1; x[sa[0]]=0; for (int i=1; i
           
            height[i]) top--; if (top) L[i]=stack[top-1]+1; else L[i]=1; stack[top++]=i; } top=1; stack[0]=len; for (int i=len; i>=1; i--) { while (top && height[stack[top-1]]>=height[i]) top--; if (top) R[i]=stack[top-1]-1; else R[i]=len; stack[top++]=i; } for (int i=2; i<=len; i++) lcp+=(long long)2*(long long)(i-L[i]+1)*(long long)(R[i]-i+1)*(long long)height[i]; printf("%lld\n",tot-lcp); return 0;}