Description
Link.
给定字符串,正整数集合 \(A,B\),满足 \(\forall u\in A,v\in B,1\le u,v\le n\)。
求 \(\sum_{i\in A}\sum_{j\in B}\text{LCP}(A,B)\)。
Solution
双倍经验是 SvT,只不过 SvT 这屑玩意儿卡常。
先反转串,然后插入 SAM。众所周知
把字符串反转后插入 SAM 后,两个原串的后缀在 parent tree 上的 \(\text{LCA}\) 是这两个后缀的 \(\text{LCP}\)。
然后你就可以搞两个 DP,分别跑 \(A\) 子树大小,\(B\) 子树大小。
注意根节点需要特殊处理,因为我们是跨子树跑的 DP。不过 SvT 不需要,不知道是不是我的问题(应该就是)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,dfn[500010],fa[500010][21],dep[500010],sjc,pos[200010],onepower[500010],anopower[500010],onef[500010],anof[500010];
char s[200010];
LL ans;
struct SuffixAutomaton
{
#define ID(c) ((c)-'a')
vector<int> e[500010];
int n,cntot,las,len[500010],pre[500010],ch[500010][26];
char s[200010];
void init(int _n,char c[])
{
n=_n;
for(int i=1;i<=n;++i) s[i]=c[i];
cntot=las=1;
}
void extend(char c)
{
int cur=++cntot,one=las,ano=0;
len[cur]=len[las]+1,las=cur;
while(one&&!ch[one][ID(c)]) ch[one][ID(c)]=cur,one=pre[one];
if(one==0) pre[cur]=1;
else
{
ano=ch[one][ID(c)];
if(len[one]+1==len[ano]) pre[cur]=ano;
else
{
int clone=++cntot;
len[clone]=len[one]+1;
pre[clone]=pre[ano];
memcpy(ch[clone],ch[ano],sizeof(ch[ano]));
while(one&&ch[one][ID(c)]==ano) ch[one][ID(c)]=clone,one=pre[one];
pre[ano]=pre[cur]=clone;
}
}
}
void build()
{
for(int i=1;i<=n;++i) extend(s[i]),pos[i]=las;
for(int i=2;i<=cntot;++i) e[pre[i]].emplace_back(i);
}
}SAM;
void dfs(int x,int las)
{
dfn[x]=++sjc,fa[x][0]=las,dep[x]=dep[las]+1;
for(int i=1;i^21;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int y : SAM.e[x]) dfs(y,x);
}
int LCA(int one,int ano)
{
if(dep[one]<dep[ano]) swap(one,ano);
for(int i=20;~i;--i) if(dep[fa[one][i]]>=dep[ano]) one=fa[one][i];
if(one^ano)
{
for(int i=20;~i;--i) if(fa[one][i]^fa[ano][i]) one=fa[one][i],ano=fa[ano][i];
return fa[one][0];
}
else return one;
}
bool cmp(int one,int ano){return dfn[one]<dfn[ano];}
struct VirtualTree
{
vector<int> e[500010];
vector<int> build(vector<int> poi)
{
sort(poi.begin(),poi.end(),cmp);
poi.erase(unique(poi.begin(),poi.end()),poi.end());
int len=poi.size();
for(int i=1;i<len;++i) poi.push_back(LCA(poi[i-1],poi[i]));
sort(poi.begin(),poi.end(),cmp);
poi.erase(unique(poi.begin(),poi.end()),poi.end());
len=poi.size();
for(int i=1;i<len;++i) e[LCA(poi[i-1],poi[i])].push_back(poi[i]);
return poi;
}
}VRT;
template<class T>
void read(T &hhh)
{
T x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
if(~f) hhh=x;
else hhh=-x;
}
template<class T>
void write(T x,char las='\n')
{
static int st[100],top=0;
if(x<0) putchar('-'),x=-x;
do st[++top]=x%10,x/=10; while(x);
while(top) putchar(st[top--]^'0');
putchar(las);
}
void exdfs(int x)
{
for(int y : VRT.e[x]) exdfs(y),onef[x]+=onef[y],anof[x]+=anof[y];
for(int y : VRT.e[x]) ans+=(LL)SAM.len[x]*(onef[x]-onef[y])*anof[y];
ans+=(LL)((onepower[x]&anopower[x])+onepower[x]*anof[x]+anopower[x]*onef[x])*SAM.len[x];
onef[x]+=onepower[x],anof[x]+=anopower[x];
}
int main()
{
read(n),read(m);
scanf("%s",s+1);
reverse(s+1,s+n+1);
SAM.init(n,s),SAM.build();
dfs(1,0);
while(m--)
{
int ones,anos,x;
read(ones),read(anos);
vector<int> key,tmp;
while(ones--) read(x),key.push_back(pos[n-x+1]),onepower[pos[n-x+1]]=1;
while(anos--) read(x),key.push_back(pos[n-x+1]),anopower[pos[n-x+1]]=1;
tmp=VRT.build(key);
ans=0,exdfs(tmp[0]);
write(ans);
for(int now : tmp) onef[now]=anof[now]=0,VRT.e[now].clear(),onepower[now]=anopower[now]=0;
}
return 0;
}