题目描述
记 $lcp(i,j)$ 表示 $i$ 表示 $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])]$ 即可.
#include#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]