题解 CF1073G 【Yet Another LCP Problem】
万弘
2020-08-09 14:46:04
## CF1073G
题意：求$\sum_i^{|A|}\sum_j^{|B|}\operatorname{LCP}(\operatorname{suf}(a_i),\operatorname{suf}(b_j))$. $\operatorname{suf}(x)$表示$[x...n]$这个后缀.
首先两后缀的 LCP 即为其对应终止节点在后缀树上的 LCA 的状态，那么显然有 LCP 的长度即为后缀树上 LCA 的深度（表示的状态的长度）
那么问题转化为，给两个点集 $A,B,$求
$$
\sum_{a\in A}\sum_{b\in B}\operatorname{dep}(\operatorname{LCA}(a,b))
$$
这就很裸了吧，就是 [GXOI/GZOI2019]旧词 那题的套路。对于每个 $b$,将其到根的路径上每个点的点权+1，$a$ 的贡献就转化为到根的路径上点权和。直接 LCT/树剖维护就好了。
两个小细节：
1. 可以用 SAM建后缀树。
2. 后缀树是经过压缩的，LCA的深度并不直接是根到他的距离，而应是其表示的状态的长度。
同时那些被压掉的点也是有贡献的，但这些点没有必要真的去修改点权，直接加到下面连的没有被压掉的点上就好了，就变成链上每个点加定值，询问链和，用树剖+线段树/LCT维护。
PS：其实用 LCT 写会短很多~~但我写挂了~~
```cpp
#define MAXN 400011
struct SAM
{
int t[MAXN][26],pre[MAXN],len[MAXN];
int last,tot;
SAM(){tot=last=1;}
void insert(int w)
{
int pos=last,cur=++tot;
len[cur]=len[pos]+1,last=cur;
while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos];
if(!pos){pre[cur]=1;return;}
int nxt=t[pos][w];
if(len[nxt]==len[pos]+1)pre[cur]=nxt;
else
{
int tmp=++tot;
len[tmp]=len[pos]+1;
memcpy(t[tmp],t[nxt],sizeof t[nxt]);
pre[tmp]=pre[nxt],pre[nxt]=pre[cur]=tmp;
while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos];
}
}
}sam;
struct Segment_Tree
{
struct node
{
ll sum,k,tag;
}t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
void pushdown(un l,un r,un num)
{
if(!rt.tag)return;
un mid=(l+r)>>1;
tl.sum+=tl.k*rt.tag,tl.tag+=rt.tag;
tr.sum+=tr.k*rt.tag,tr.tag+=rt.tag;
rt.tag=0;
}
void build(int* arr,un l=1,un r=sam.tot,un num=1)
{
if(l==r)rt.k=arr[l];
else
{
un mid=(l+r)>>1;
build(arr,l,mid,num<<1),build(arr,mid+1,r,num<<1|1);
rt.k=tl.k+tr.k;
}
}
void modify(un ql,un qr,ll k,un l=1,un r=sam.tot,un num=1)
{
if(ql<=l&&r<=qr){rt.sum+=k*rt.k,rt.tag+=k;return;}
pushdown(l,r,num);
un mid=(l+r)>>1;
if(ql<=mid)modify(ql,qr,k,l,mid,num<<1);
if(qr>mid)modify(ql,qr,k,mid+1,r,num<<1|1);
rt.sum=tl.sum+tr.sum;
}
ll Qsum(un ql,un qr,un l=1,un r=sam.tot,un num=1)
{
if(ql<=l&&r<=qr)return rt.sum;
pushdown(l,r,num);
un mid=(l+r)>>1;ll ans=0;
if(ql<=mid)ans+=Qsum(ql,qr,l,mid,num<<1);
if(qr>mid)ans+=Qsum(ql,qr,mid+1,r,num<<1|1);
return ans;
}
}sgt;
struct edge{int v,nxt;}e[MAXN];
int cnt=0,last[MAXN];
void adde(int u,int v){e[++cnt].v=v,e[cnt].nxt=last[u],last[u]=cnt;}
int size[MAXN],fa[MAXN],mson[MAXN];
void dfs1(int u)
{
size[u]=1;
for(int i=last[u];i;i=e[i].nxt)
{
int v=e[i].v;
fa[v]=u,dfs1(v);
if(size[v]>size[mson[u]])mson[u]=v;
size[u]+=size[v];
}
}
int top[MAXN],dfn[MAXN],w[MAXN], cur=0;
void dfs2(int u,int now_top)
{
top[u]=now_top,dfn[u]=++cur,w[cur]=sam.len[u]-sam.len[fa[u]];
if(mson[u])dfs2(mson[u],now_top);
for(int i=last[u];i;i=e[i].nxt)
if(e[i].v!=mson[u])dfs2(e[i].v,e[i].v);
}
void add_to_root(int u,int k)
{
while(u)sgt.modify(dfn[top[u]],dfn[u],k),u=fa[top[u]];
}
ll Qsum_to_root(int u)
{
ll res=0;
while(u)res+=sgt.Qsum(dfn[top[u]],dfn[u]),u=fa[top[u]];
return res;
}
int ed[MAXN],a[MAXN],b[MAXN];
char s[MAXN];
int main()
{
int n=read(),m=read();scanf("%s",s+1);
for(int i=n;i;--i)sam.insert(s[i]-'a'),ed[i]=sam.last;//建反串SAM
for(int i=2;i<=sam.tot;++i)adde(sam.pre[i],i);//建后缀树
dfs1(1),dfs2(1,1),sgt.build(w);
while(m--)
{
int k=read(),l=read();
ll ans=0;
for(int i=1;i<=k;++i)a[i]=read();
for(int i=1;i<=l;++i)b[i]=read(),add_to_root(ed[b[i]],1);
for(int i=1;i<=k;++i)ans+=Qsum_to_root(ed[a[i]]);
for(int i=1;i<=l;++i)add_to_root(ed[b[i]],-1);
printf("%lld\n",ans);
}
return 0;
}
```