Time:2016.08.15 Author:xiaoyimi 转载注明出处谢谢 如果有不明白的地方可以在下面评论问我
传送门 思路： 建立后缀数组求出Height 如果说对每次询问暴力求LCP累加的话，每次询问的复杂度是O (n2) ，显然不能接受 考虑每次询问按rank排序后用单调栈维护，使栈中的元素所表示的LCP单调不减 栈中元素的LCP实际上是一段连续元素（至少为1）的LCP值，所以要记录这段连续元素的siz （siz[i]指元素i所指向的LCP的元素个数，就是这个LCP要被计算的次数） 记录临时变量sum和相邻后缀间的LCP即可 复杂度 O(nlogn+mlogn) 注意： 好久没写后缀数组了，板子敲了半天敲不对，height和rank的下标弄不对 老年人 代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<stack> #include<cmath> #define M 500003 #define LL long long using namespace std; int n,m,t; int cnt[M],rank[M],sa[M],id[M],w[M],tmp[M],height[M],q[M<<3],siz[M]; int f[M][20]; stack <int> S; bool cmp(int x,int y){return rank[x-1]<rank[y-1];} int in() { char ch=getchar();int t=0; while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) t=(t<<3)+(t<<1)+ch-48,ch=getchar(); return t; } void SA(int len,int up) { int *rk=rank,p=0,*t=tmp,d=1; for (int i=0;i<len;i++) cnt[rk[i]=w[i]]++; for (int i=1;i<up;i++) cnt[i]+=cnt[i-1]; for (int i=len-1;i>=0;i--) sa[--cnt[rk[i]]]=i; for (;;) { for (int i=len-d;i<len;i++) id[p++]=i; for (int i=0;i<len;i++) if (sa[i]>=d) id[p++]=sa[i]-d; for (int i=0;i<up;i++) cnt[i]=0; for (int i=0;i<len;i++) cnt[t[i]=rk[id[i]]]++; for (int i=1;i<up;i++) cnt[i]+=cnt[i-1]; for (int i=len-1;i>=0;i--) sa[--cnt[t[i]]]=id[i]; swap(t,rk); p=1; rk[sa[0]]=0; for (int i=0;i<len-1;i++) if (sa[i]+d<len&&sa[i+1]+d<len&&t[sa[i]]==t[sa[i+1]]&&t[sa[i]+d]==t[sa[i+1]+d]) rk[sa[i+1]]=p-1; else rk[sa[i+1]]=p++; if (p==len) break; d<<=1;up=p;p=0; } } void Height(int len) { for (int i=1;i<=len;i++) rank[sa[i]]=i; int k=0,x; for (int i=0;i<len;i++) { k=max(k-1,0); x=sa[rank[i]-1]; while (w[i+k]==w[x+k]) k++; height[rank[i]]=k; } } int LCP(int x,int y) { if (x>y) swap(x,y); int p=log2(y-x); return min(f[x+1][p],f[y-(1<<p)+1][p]); } main() { n=in();m=in(); for (int i=0;i<n;i++) { char ch=getchar(); while (ch>'z'||ch<'a') ch=getchar(); w[i]=ch-'a'+1; } SA(n+1,28); Height(n); for (int i=1;i<=n;i++) f[i][0]=height[i]; for (int i=1;(1<<i)<=n;i++) for (int j=1;j+(1<<i)-1<=n;j++) f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]); for (;m;m--) { t=in(); for (int i=1;i<=t;i++) q[i]=in(); sort(q+1,q+t+1,cmp); t=unique(q+1,q+t+1)-q-1; LL ans=0,sum=0; for (;!S.empty();S.pop()); for (int i=2;i<=t;i++) { siz[i]=1; tmp[i]=LCP(rank[q[i-1]-1],rank[q[i]-1]); while (!S.empty()&&tmp[S.top()]>tmp[i]) sum=sum-(LL)(tmp[S.top()]-tmp[i])*siz[S.top()], siz[i]+=siz[S.top()], S.pop(); sum+=tmp[i];ans+=sum; S.push(i); } printf("%lld\n",ans); } }