LINK：SvT
给出一个字符串 给出若干个后缀 求两两后缀之间的LCP.
考虑SAM 要把字符串反着建立SAM 考虑两个后缀的LCP 其实就是在parent树上两点的LCA的长度.
可以发现建立出虚树 在虚树上跑一遍dp即可。复杂度询问数*log.
考虑SA 直接求出SA 按照各个后缀的排名排序加入对答案的贡献中 利用单调队列来维护新加入的后缀和之前的后缀的LCP 即可O(1)计算答案.
不过需要ST表查两个后缀之间的LCP.
代码复杂度的话 两者差不多 SAM还是要简单一些的 所以这里考虑写SA /cy.
const int MAXN=500010<<1;
int n,m,Q,top;
char a[MAXN];
int f[MAXN][21],b[MAXN*3],Log[MAXN],s[MAXN],w[MAXN];
int x[MAXN],y[MAXN],h[MAXN],c[MAXN],sa[MAXN],rk[MAXN];
inline void SA()
{
m=150;
rep(1,n,i)++c[x[i]=a[i]];
rep(1,m,i)c[i]+=c[i-1];
rep(1,n,i)sa[c[x[i]]--]=i;
for(int k=1;k<=n;k=k<<1)
{
int num=0;
rep(n-k+1,n,i)y[++num]=i;
rep(1,n,i)if(sa[i]>k)y[++num]=sa[i]-k;
rep(1,m,i)c[i]=0;
rep(1,n,i)++c[x[i]];
rep(1,m,i)c[i]+=c[i-1];
fep(n,1,i)sa[c[x[y[i]]]--]=y[i];
rep(1,n,i)y[i]=x[i],x[i]=0;
x[sa[1]]=num=1;
rep(2,n,i)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?num:++num;
if(num==n)break;
m=num;
}
rep(1,n,i)rk[sa[i]]=i;
}
inline int cmp(int x,int y){return rk[x]<rk[y];}
inline void get_Height()
{
int k=0;
rep(1,n,i)
{
if(rk[i]==1)continue;
if(k)--k;
int j=sa[rk[i]-1];
while(a[i+k]==a[j+k])++k;
h[rk[i]]=k;
}
}
inline int LCP(int x,int y)
{
x=rk[x];y=rk[y];
--y;int w=Log[y-x+1];
return min(f[x][w],f[y-(1<<w)+1][w]);
}
int main()
{
freopen("1.in","r",stdin);
gt(n);gt(Q);gc(a);
SA();get_Height();
rep(2,n,i)
{
f[i-1][0]=h[i];
Log[i]=Log[i>>1]+1;
}
rep(1,Log[n-1],j)
rep(1,n-(1<<j),i)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
rep(1,Q,i)
{
int get(x);ll cnt=0,ans=0,last=0;
rep(1,x,j)get(b[j]);
sort(b+1,b+1+x,cmp);
top=0;last=b[1];
rep(2,x,j)
{
if(b[j]==b[j-1])continue;
int len=LCP(last,b[j]),num=1;
while(top&&len<=s[top])
{
cnt-=(ll)s[top]*w[top];
num+=w[top];--top;
}
s[++top]=len;cnt+=(ll)num*len;
w[top]=num;ans+=cnt;last=b[j];
}
putl(ans);
}
return 0;
}