题目
Description
(我并不想告诉你题目名字是什么鬼)
有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].
现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(Longest Common Prefix)的长度之和.一对后缀之间的LCP长度仅统计一遍.
Input
第一行两个正整数n,m,分别表示S的长度以及询问的次数.
接下来一行有一个字符串S.
接下来有m组询问,对于每一组询问,均按照以下格式在一行内给出:
首先是一个整数t,表示共有多少个后缀.接下来t个整数分别表示t个后缀在字符串S中的出现位置.
Output
对于每一组询问,输出一行一个整数,表示该组询问的答案.由于答案可能很大,仅需要输出这个答案对于23333333333333333(一个巨大的质数)取模的余数.
Sample Input
7 3
popoqqq
1 4
2 3 5
4 1 2 5 6
Sample Output
0
0
2
Hint
样例解释:
对于询问一,只有一个后缀”oqqq”,因此答案为0.
对于询问二,有两个后缀”poqqq”以及”qqq”,两个后缀之间的LCP为0,因此答案为0.
对于询问三,有四个后缀”popoqqq”,”opoqqq”,”qqq”,”qq”,其中只有”qqq”,”qq”两个后缀之间的LCP不为0,且长度为2,因此答案为2.
对于100%的测试数据,有$S\le 5\times 10^5$,且$\sum t\le 3\times 10^6$.
特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次.
题解
这个模数给的真的很灵性啊……
题意就是要求一堆后缀的$lcp$，所以把字符串倒过来就成了求前缀的$lcs$（最长公共后缀Longest Common Suffix），即两两状态的$LCA$
建出虚树来后，从下往上依次处理每个状态能被做$LCA$多少次即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e6+5;
const LL mod=23333333333333333ll;
int n,m;
int T[MAX],id[MAX],use[MAX];
char a[MAX];
struct SAM{
struct p{
int x,y;
}c[MAX<<1];
int l,r,L,num,cnt,Top;
LL ans;
int h[MAX],len[MAX],fa[MAX],siz[MAX],pos[MAX],top[MAX],Son[MAX],d[MAX],st[MAX];
int son[MAX][26];
SAM() {l=r=1;}
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num;}
void ADD(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
c[++num]=(p){h[x],y},h[x]=num;
}
void ins(int x,int id)
{
int tt=r;
len[r=++l]=++L,pos[id]=r;
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
for(int i=0;i<26;++i)
son[l][i]=son[qwq][i];
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void dfs(int x=1)
{
d[x]=d[fa[x]]+(siz[x]=1);
for(int i=h[x];i;i=c[i].x)
{
dfs(c[i].y),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[Son[x]]) Son[x]=c[i].y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,id[x]=++cnt;
if(!Son[x]) return;
dfs1(Son[x],tp);
for(int i=h[x];i;i=c[i].x)
if(c[i].y^Son[x]) dfs1(c[i].y,c[i].y);
h[x]=0;
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
return d[x]>d[y]?y:x;
}
int GET_DIS(int x,int y) {return d[x]+d[y]-(d[LCA(x,y)]<<1);}
void Init()
{
for(int i=2;i<=l;++i)
add(fa[i],i);
dfs(),dfs1();
}
void Dfs(int x=1,int fa=0)
{
siz[x]=use[x];
LL Ans=siz[x];
for(int i=h[x];i;i=c[i].x)
if(c[i].y^fa) Dfs(c[i].y,x),siz[x]+=siz[c[i].y],ans=(ans+Ans*siz[c[i].y]*len[x]%mod)%mod,Ans+=siz[c[i].y];
h[x]=use[x]=0;
}
void Work(int k)
{
num=ans=0,st[Top=1]=1;
for(int i=1,lca;i<=k;++i)
{
lca=LCA(st[Top],T[i]);
while(Top>1&&d[st[Top-1]]>d[lca]) ADD(st[Top],st[Top-1]),--Top;
while(Top&&d[st[Top]]>d[lca]) ADD(lca,st[Top]),--Top;
if(!Top||d[lca]>d[st[Top]]) st[++Top]=lca;
if(T[i]!=st[Top]) st[++Top]=T[i];
}
while(Top>1) ADD(st[Top],st[Top-1]),--Top;
Dfs(),printf("%lld\n",ans);
}
}_S;
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
bool cmp(int a,int b) {return id[a]<id[b];}
int main()
{
n=read(),m=read(),scanf("%s",a+1);
reverse(a+1,a+1+n);
for(int i=1;i<=n;++i)
_S.ins(a[i]-'a',n-i+1);
_S.Init();
for(int i=1,k;i<=m;++i)
{
k=read();
for(int j=1;j<=k;++j)
use[T[j]=_S.pos[read()]]=1;
sort(T+1,T+1+k,cmp),_S.Work(k);
}
return 0;
}
