题目描述
记 $lcp(i,j)$ 表示 $i$ 表示 $i$ 这个后缀和 $j$ 这个后缀的最长公共后缀长度
给定一个字符串，每次询问的时候给出两个正整数集合 $A$ 和 $B$，求
$\sum_{i\in A,j\in B}lcp(i,j)$ 的值.
给定一个字符串，每次询问的时候给出两个正整数集合 $A$ 和 $B$，求
$\sum_{i\in A,j\in B}lcp(i,j)$ 的值.
题解： 对反串建立后缀自动机.
这样，任意两个后缀树节点所代表的字符串的 $LCP$ 值就是两点最近公共祖先在自动机中的 $len$ 值.
问题转化为 $\sum_{i\in A,j\in B}len[LCA(id[i],id[j])]$
其中 $id[i]$ 表示 $S[1...i]$ 所表示的字符串在自动机中的节点.
询问次数很多，不过 $\sum A+B$ 不会很大.
用虚树统计 $\sum_{i\in A,j\in B}len[LCA(id[i],id[j])]$ 即可.
问题转化为 $\sum_{i\in A,j\in B}len[LCA(id[i],id[j])]$
其中 $id[i]$ 表示 $S[1...i]$ 所表示的字符串在自动机中的节点.
询问次数很多，不过 $\sum A+B$ 不会很大.
用虚树统计 $\sum_{i\in A,j\in B}len[LCA(id[i],id[j])]$ 即可.
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 400004
#define ll long long
using namespace std;
int edges,n,Q;
int hd[maxn],to[maxn],nex[maxn],tr[maxn];
char str[maxn];
void addedge(int u,int v,int c)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
namespace SAM
{
int last, tot;
int len[maxn],f[maxn],trans[maxn][27];
void init() { last=tot=1; }
int extend(int c)
{
int np=++tot,p=last;
len[np]=len[p]+1,last=np;
while(p&&!trans[p][c]) trans[p][c]=np, p=f[p];
if(!p) f[np]=1;
else
{
int q=trans[p][c];
if(len[q]==len[p]+1) f[np]=q;
else
{
int nq=++tot;
len[nq]=len[p]+1;
memcpy(trans[nq],trans[q],sizeof(trans[q]));
f[nq]=f[q],f[q]=f[np]=nq;
while(p&&trans[p][c]==q) trans[p][c]=nq,p=f[p];
}
}
return np;
}
void build()
{
for(int i=2;i<=tot;++i) addedge(f[i],i,len[f[i]]-len[i]);
}
}
int tim;
int dfn[maxn],Top[maxn],hson[maxn],siz[maxn],fa[maxn],dis[maxn];
void dfs1(int u,int ff)
{
fa[u]=ff,siz[u]=1,dfn[u]=++tim,dis[u]=dis[ff]+1;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==ff) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]]) hson[u]=v;
}
}
void dfs2(int u,int tp)
{
Top[u]=tp;
if(hson[u]) dfs2(hson[u],tp);
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==fa[u]||v==hson[u]) continue;
dfs2(v,v);
}
}
int LCA(int x,int y)
{
while(Top[x]!=Top[y])
{
dis[Top[x]]>dis[Top[y]]?x=fa[Top[x]]:y=fa[Top[y]];
}
return dis[x]<dis[y]?x:y;
}
vector<int>G[maxn];
ll ans=0;
int t=0,tot=0;
int arr[maxn],brr[maxn],A[maxn<<1],mk[maxn],mka[maxn],mkb[maxn],sizea[maxn],sizeb[maxn],S[maxn];
bool cmp(int i,int j)
{
return dfn[i]<dfn[j];
}
void addvir(int x,int y)
{
G[x].push_back(y);
}
void insert(int x)
{
if(t<=1) { S[++t]=x; return; }
int lca=LCA(S[t],x);
if(lca==S[t]) { S[++t]=x; return; }
while(t>1&&dis[S[t-1]]>=dis[lca]) addvir(S[t-1],S[t]),--t;
if(S[t]!=lca) addvir(lca,S[t]),S[t]=lca;
S[++t]=x;
}
void DP(int x)
{
for(int i=0;i<G[x].size();++i)
DP(G[x][i]), sizea[x]+=sizea[G[x][i]], sizeb[x]+=sizeb[G[x][i]];
for(int i=0;i<G[x].size();++i)
{
ans+=1ll*(sizea[x]-sizea[G[x][i]])*sizeb[G[x][i]]*SAM::len[x];
}
ans+=(1ll*mka[x]*mkb[x]+1ll*mka[x]*sizeb[x]+1ll*mkb[x]*sizea[x])*SAM::len[x];
sizea[x]+=mka[x],sizeb[x]+=mkb[x];
}
void erase(int x)
{
mka[x]=mkb[x]=sizea[x]=sizeb[x]=0;
for(int i=0;i<G[x].size();++i) erase(G[x][i]);
G[x].clear();
}
void work()
{
tot=0;
int k1,k2;
scanf("%d%d",&k1,&k2);
for(int i=1;i<=k1;++i) scanf("%d",&arr[i]),A[++tot]=tr[arr[i]],mka[tr[arr[i]]]=1;
for(int i=1;i<=k2;++i) scanf("%d",&brr[i]),A[++tot]=tr[brr[i]],mkb[tr[brr[i]]]=1;
sort(A+1,A+1+tot,cmp);
tot=unique(&A[1],&A[tot+1])-A-1;
t=ans=0;
if(A[1]!=1) S[t=1]=1;
for(int i=1;i<=tot;++i) insert(A[i]);
while(t>1) addvir(S[t-1],S[t]),--t;
DP(1);
printf("%I64d\n",ans);
erase(1);
}
int main()
{
// setIO("input");
scanf("%d%d%s",&n,&Q,str+1);
SAM::init();
for(int i=n;i>=1;--i) tr[i]=SAM::extend(str[i]-'a');
SAM::build();
dfs1(1,0),dfs2(1,1);
for(int i=1;i<=Q;++i) work();
return 0;
}