后缀数组

　　这题题面给的暗示性就很强啊……一看就是要用后缀xx一家的算法，由于本蒻只会后缀数组所以就拿后缀数组写了。

　　这个题目的要求……我们很明显可以直接预处理出来T(i)+T(j)的总和，为n*(n-1)*(n+1)/2。（应该挺容易推的吧？自己画一下（样例）：当i为1的时候，j可以为2、3、4、5。则1算了4次，2~5各一次；然后2算三次，3~5算一次；3算两次，4、5算一次；4算一次，5算1次。总共加起来，每个数各算了4次。1~5的和是n*(n+1)/2，总共算了(n-1)次，再乘一下就行了。）

　　难点在于LCP的减……这个地方我们可以直接在height数组上搞，我们可以发现，每一对(i,j)都对应了height数组上的一段区间、甚至是点！（当i,j两个子串rank相连的时候）那么同样的，每一个height数组上的一段区间（点）也对应我们要求的一个LCP。

　　这样有什么好处呢？原本暴力的做法是枚举i，j，用RMQ算LCP，再减；而现在我们转换成直接算LCP，而不用考虑是谁和谁的LCP（事实上并不会落下任何一个），这样问题就简单多了：利用求LCP的特殊性，我们对于每一个height[i]，都能找到一段区间[l,r]，使得height[i]=min(height[l]~height[r])。额意思就是 i 是[l,r]这个区间上的最小值。这样LCP=height[i]的对数为 (l-i+1)*(r-i+1) 【ps.我们事先说过，[i,i]这样的一个点也算】也就是说我们的答案里可以减去 2*height[i]*(l-i+1)*(r-i+1) 这样一个值。

　　但是！！这样会有重复计算的情况：

　　　　举个栗子：height为 1 2 3 1 2 1 1时，第一个1的[l,r]区间为[1,7]，第二个为[1,7]，明显有重复计算了（[l,i] 和 [i,r]这两段有重叠，也就是计算了两次）所以我们在计算对于每个 i 所能到达的[l,r]区间时，遇到相等元素，必须分开处理：比如如果向右遇到相等元素则可以继续扩展，而向左遇到则停止。（当然你反过来做应该也可以……）

　　现在分析清楚了，最后的问题是：怎么算l[i],r[i]，也就是每个height[i]对应的区间？

　　这里我们可以利用一个叫做单调栈的东西，维护栈里的元素height[j]都比当前的height[j]要小，如果大则弹出，这样就能O(N)求出所有的l[i],r[i]了。

错误：1.计算答案的时候，必须要在乘法中加上 (LL)类型强制转换，否则会出错。

　　　2.在栈为空的时候，意味着左边（右边）所有的元素都比当前的要大，则范围应为从端点(1或n)到i的整个区间，而不是i (见代码)

  1 /**************************************************************
  2     Problem: 3238
  3     User: ProgrammingApe
  4     Language: C++
  5     Result: Accepted
  6     Time:3416 ms
  7     Memory:23244 kb
  8 ****************************************************************/
  9  
 10 //练习六 T1 闫鸿宇
 11 //BZOJ 3238
 12 #include<cmath>
 13 #include<cstdio>
 14 #include<cstring>
 15 #include<cstdlib>
 16 #include<iostream>
 17 #include<algorithm>
 18 #define rep(i,n) for(int i=0;i<n;++i)
 19 #define F(i,j,n) for(int i=j;i<=n;++i)
 20 #define D(i,j,n) for(int i=j;i>=n;--i)
 21 using namespace std;
 22 const int N=500010;
 23 typedef long long LL;
 24 //#define debug
 25 int n,m,sa[N],c[N],wa[N],wb[N],wv[N],rank[N],height[N],l[N],r[N];
 26  
 27 int cmp(int *r,int a,int b,int l){
 28     return r[a]==r[b] && r[a+l]==r[b+l];
 29 }
 30  
 31 void DA(char *s,int *sa,int n,int m){
 32     int i,j,p,*x=wa,*y=wb;
 33     rep(i,m) c[i]=0;
 34     rep(i,n) c[x[i]=s[i]]++;
 35     F(i,1,m-1) c[i]+=c[i-1];
 36     D(i,n-1,0) sa[--c[x[i]]]=i;
 37     for(p=0,j=1;p<n;j<<=1,m=p){
 38         for(p=0,i=n-j;i<n;++i) y[p++]=i;
 39         rep(i,n) if (sa[i]>=j) y[p++]=sa[i]-j;
 40          
 41         rep(i,m) c[i]=0;
 42         rep(i,n) c[x[y[i]]]++;
 43         F(i,1,m-1) c[i]+=c[i-1];
 44         D(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
 45         swap(x,y); p=1; x[sa[0]]=0;
 46         F(i,1,n-1) x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;
 47     }
 48 }
 49  
 50 void calheight(char *s,int *sa,int n){
 51     int k=0;
 52     F(i,1,n) rank[sa[i]]=i;
 53     rep(i,n){
 54         if (k) k--;
 55         int j=sa[rank[i]-1];
 56         while(s[i+k]==s[j+k]) k++;
 57         height[rank[i]]=k;
 58     }
 59 }
 60  
 61 int q[N],st[N],top=0;
 62 char s[N];
 63 int main(){
 64 //  freopen("input.txt","r",stdin);
 65 //  freopen("output.txt","w",stdout);
 66     scanf("%s",&s);
 67     int n=strlen(s);
 68     rep(i,n) s[i]=s[i]-'a'+2;
 69     s[n]=0;
 70      
 71     DA(s,sa,n+1,30);
 72     calheight(s,sa,n);
 73     height[1]=height[n+1]=0;
 74  
 75     LL ans=(LL)((LL)n*(n-1)*(n+1))/2,delta=0;  
 76     //T(i) 和 T(j) 的总和
 77      
 78     top=0;
 79     st[top++]=1;
 80     F(i,1,n){
 81         while (top && height[st[top-1]] > height[i]) top--;
 82         if (top) l[i]=st[top-1]+1;
 83         else l[i]=1;
 84         st[top++]=i;
 85     }
 86      
 87     top=0;
 88     st[top++]=n; r[n]=n;
 89     D(i,n,1){
 90         while (top && height[st[top-1]] >= height[i]) top--;
 91         if (top) r[i]=st[top-1]-1;
 92         else r[i]=n;//!!!!
 93         st[top++]=i;
 94     }
 95      
 96     #ifdef debug
 97     F(i,1,n) printf("%d ",height[i]);
 98     printf("
");
 99     F(i,1,n) printf("%d ",l[i]);
100     printf("
");
101     F(i,1,n) printf("%d ",r[i]);
102     printf("
");
103     #endif
104     F(i,2,n){
105         delta+=(LL)2*(LL)height[i]*(LL)(i-l[i]+1)*(LL)(r[i]-i+1);
106         #ifdef debug
107         printf("%d * %d * %d = %d
",height[i],i-l[i]+1,r[i]-i+1,height[i]*(i-l[i]+1)*(r[i]-i+1));
108         #endif
109     }
110     #ifdef debug
111     printf("%lld %lld
",ans,delta);
112     #endif
113     ans-=delta;
114     printf("%lld
",ans);
115     return 0;
116 }

View Code