因为涉及到对模板的理解，所以就着代码看会好一些。
让那些坚决不颓代码的人受委屈了。
我是对着wzz的板子默写的，可能不完全一样啊。
还有代码注释里都是我个人的理解，不保证正确，但欢迎指正。
可以有选择的浏览，单调栈的那个非模板部分可以不看，自己想。
因为写的稍微有点详细所以在网页上极丑，粘到自己gedit上看吧。
1 #include<cstdio>
2 #include<algorithm>
3 #define int long long
4 char s[500005];
5 int x[500005],y[500005],sa[500005],rk[500005],l=1,c[500005],m=27,h[500005];
6 int sta[500005],sta2[500005],top,ans,tr[500005],tl[500005];
7 main(){
8 scanf("%s",s);
9 while(s[l]) l++;//统计长度。在末尾加上了一个空字符
10 for(int i=0;i<=l;++i) c[s[i]?x[i]=s[i]-'a'+1:0]++;//统计各字符出现次数，顺便把字符串s转化为数串x
11 for(int i=0;i<=m;++i) c[i]+=c[i-1];//累加得到出现次数的前缀和，相当与划分出了多个区间
12 for(int i=l;~i;--i) sa[--c[x[i]]]=i;//初步确定每个范围里有哪些串，但内部排名未知
13 for(int len=1,p=0;len<=l+1;len<<=1,p=0){//枚举前后两截（二元组）的长度，倍增求解每个串在长度为len<<1的所有串中的排名
14 for(int i=l;i>=l-len+1;--i) y[p++]=i;//没有后半截的直接记录，y数组存的是前半截（也就是整个串）的起始位置，y有序因为空字符的字典序最小
15 for(int i=0;i<=l;++i) if(sa[i]>=len) y[p++]=sa[i]-len;//有后半截的，那就记录下它对应的左半截，注意y已经是后半截有序的
16 for(int i=0;i<=m;++i) c[i]=0;//清空字符出现次数
17 for(int i=0;i<=l;++i) c[x[i]]++;//重新累加每个长度为len的字符串的出现次数
18 for(int i=1;i<=m;++i) c[i]+=c[i-1];//还是前缀和，完全和循环外面的一样，划分出大致区间
19 for(int i=l;~i;--i) sa[--c[x[y[i]]]]=y[i];//对于每个串的前半截讨论其排名，前半截有序了，排名相同的按后半截也拍好序了（因为y已经有序）
20 p=0;std::swap(x,y); x[sa[0]]=0;//清空p，xy数组滚动交换，确定排名第0的串是一个空串
21 for(int i=1;i<=l;++i) x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len]?p:++p;//类似离散化，求出已经区分开的串的种数，并更新字符串和字典序排名
22 if(p==l)break;else m=p;//如果已经全部区分开了，可以跳出循环，否则更新串种数然后继续区分
23 }
24 for(int i=0;i<=l;++i) rk[sa[i]]=i;//求出sa的逆数组，表示排名为i的串的开始位置
25 for(int i=0,k=0;i<=l;h[rk[i++]]=k,k=k?k-1:0) while(s[i+k]==s[sa[rk[i]-1]+k]) k++;//求height，s[i+k]可以写作s[sa[rk[i]]+k]更好理解，注意h[1]是无用的因为sa[1]是空串
26 //性质：排名为i,j(i<j)的后缀的lcp为min{height[k]|i+1≤k≤j}
27 //转化：已知一段序列，求所有字串的最小值的和--两次单调栈（内部元素是底小顶大），求解左右多大的区间能以这个值为最小值
28 sta[0]=-3;h[l+1]=-2;h[1]=-1;//与后面的弹栈元素等有关，-3直接入栈压底防止弹栈弹多了，其余两个都是用来强制所有正常元素弹栈
29 for(int i=2;i<=l+1;++i){//注意这里到了l+1,也就是用-2强制弹干净栈中所有的元素（除了压底的-3）
30 while(sta[top]>=h[i])tr[sta2[top--]]=i-1;//当一个元素被弹出，一定是遇到了右侧第一个小于等于它的元素，那么自然以此为右端点的区间内最小值为这个元素
31 sta[++top]=h[i];sta2[top]=i;//入栈，记录位置
32 }
33 for(int i=l;i;--i){//倒着单调栈，求出它能控制的左端点，用h[1]=-1强制弹栈
34 while(sta[top]>h[i])tl[sta2[top--]]=i+1;//注意这里没有等号，否则当有相等的height值时会重复计算（对于测试点abbab好像就不行）
35 sta[++top]=h[i];sta2[top]=i;
36 }
37 for(int i=2;i<=l;++i)ans+=h[i]*(tr[i]-i+1)*(i-tl[i]+1);//区间右端点在i~tr[i]内任选，左端点在tl[i]~i内任选，这时区间最小值都是h[i],记录方案数乘权值
38 printf("%lld\n",((l-1)*l*(l+1)>>1)-(ans<<1));
39 }
View Code