题解 CF1073G 【Yet Another LCP Problem】

shadowice1984

2018-11-05 16:08:10

Solution

后缀自动姬/后缀数组都能做 手懒了就打了个后缀自动姬 ____________________ ### 前置芝士:后缀自动姬 ~~不会后缀自动姬的话可以出门左转你站模板区,保教包会~~ ### 前置芝士:虚树 ~~不会虚树的话可以在你站随便找几道关于虚树的题做做,然后就会了~~ ## 本题题解 一句话题意,记lcp(i.j)表示i这个后缀和j这个后缀的最长公共前缀长度 给定一个字符串,每次询问的时候给出两个正整数集合A和B,求 $$\sum_{i \in A,j \in B}lcp(i,j)$$ 的值 ### 关于parent树的一些常识 你需要知道的事情是,后缀自动姬有n个表示前缀的节点,还有一些表示其他子串的节点,这些点共同构成了后缀自动姬 而后缀自动姬上一个节点i的right集合其实就是i子树中出现的前缀节点,如果p这个前缀节点在i的子树中出现了,那i的right集合中就有p 那么我们借此可以使用后缀自动姬来求两个前缀的最长公共后缀 假设其中一个前缀在后缀自动姬上对应的节点是u另一个节点在后缀自动姬上对应的节点是v的话,这两个前缀的最长公共后缀长度就是lca(u,v)这个节点所能表示的最长子串长度,换句话说就是lca(u,v)的len值 _______________ ### 虚树 那好了有了这个结论我们能做什么呢? 我们把原来的串反过来跑后缀自动姬,那么两个后缀在反串上就是两个前缀,而最长公共前缀也变成了最长公共后缀 那么根据我们刚才的转化就是两个节点的lca的len值 但是问题是我们的A和B是两个节点的集合,直接大力枚举点对求lca显然会tle导致gg 怎么办呢? 我们对这两个点集的并集建一个虚树出来 在虚树上dfs,假设我们dfs到了一个点p,那么我们就统计有多少个点对(u,v)满足lca(u,v)=p,然后令答案加上len(p)×点对个数就行了 怎么统计点对个数呢? 我们将所有属于A集合的点染成白色而所有属于B集合的点染成黑色,当然一些点可能没有颜色而另一些点可能既是白色又是黑色 我们令dp(u,0/1)表示u子树当中的白点和黑点的个数转移十分显然 当我们合并两个节点(u,v)其中u是v的父亲的时候,我们会发现以u为lca的点对个数多了 $$dp(u,0)dp(v,1)+dp(u,1)dp(u,0)$$ 这么多个,直接给答案贡献上就ok了 然后代码相当好写~ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=2*1e5+10;typedef long long ll; int n;int m;char mde[N];int v[2*N];int x[2*N];int ct;int al[2*N];int len[2*N]; int fa[2*N][22];int dep[2*N];int dfi[2*N];int dfo[2*N];int df; bool book[2*N];int op[4*N];int tpop;int st[2*N];int tp;int dp[2*N][2]; inline bool cmp(int a,int b){return ((a<0)?dfo[-a]:dfi[a])<((b<0)?dfo[-b]:dfi[b]);} inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} struct suffixautomaton//简易后缀自动姬模板 { int mp[2*N][30];int fa[2*N];int ct; inline void ih(){for(int i=1;i<=n;i++)len[i]=i;ct=n+1;} inline void ins(int nw,int c) { int p=(nw==1)?n+1:nw-1;for(;p&&mp[p][c]==0;p=fa[p])mp[p][c]=nw; if(p==0){fa[nw]=n+1;return;}int q=mp[p][c]; if(len[q]==len[p]+1){fa[nw]=q;return;}++ct;len[ct]=len[p]+1; for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i]; for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct;fa[ct]=fa[q];fa[q]=fa[nw]=ct; } inline void build(){for(int i=1;i<=ct;i++)if(fa[i])add(fa[i],i);} }sam; inline void dfs(int u)//倍增求lca { dfi[u]=++df; for(int i=0;fa[u][i];i++)fa[u][i+1]=fa[fa[u][i]][i];dep[u]=dep[fa[u][0]]+1; for(int i=al[u];i;i=x[i])fa[v[i]][0]=u,dfs(v[i]);dfo[u]=++df; } inline int lca(int u,int v) { if(dep[u]<dep[v])swap(u,v);for(int d=dep[u]-dep[v],i=0;d;d>>=1,i++)if(d&1)u=fa[u][i]; if(u==v)return u;for(int i=18;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int main() { scanf("%d%d",&n,&m);scanf("%s",mde+1);sam.ih();reverse(mde+1,mde+n+1); for(int i=1;i<=n;i++)sam.ins(i,mde[i]-'a'+1);sam.build();dfs(n+1); for(int z=1,k1,k2;z<=m;z++)//虚树板子 { scanf("%d%d",&k1,&k2);tpop=0; for(int i=1,t;i<=k1;i++)scanf("%d",&t),t=n-t+1,dp[t][0]=1,op[++tpop]=t,book[t]=true; for(int i=1,t;i<=k2;i++) {scanf("%d",&t),t=n-t+1,dp[t][1]=1;if(!book[t])op[++tpop]=t,book[t]=true;} sort(op+1,op+tpop+1,cmp); for(int i=1,lim=tpop,lc;i<lim;i++) {lc=lca(op[i],op[i+1]);if(!book[lc])op[++tpop]=lc,book[lc]=true;} for(int i=1;i<=tpop;i++)book[op[i]]=false; for(int i=1,lim=tpop;i<=lim;i++)op[++tpop]=-op[i];sort(op+1,op+tpop+1,cmp); ll ans=0; for(int i=1;i<=tpop;i++) if(op[i]>0){int u=op[i];st[++tp]=u;ans+=(ll)len[u]*dp[u][0]*dp[u][1];} else { if(tp==1){dp[st[tp]][0]=dp[st[tp]][1]=0;tp--;continue;} int u=st[tp];tp--;int f=st[tp]; ans+=(ll)len[f]*((ll)dp[f][0]*dp[u][1]+(ll)dp[f][1]*dp[u][0]); dp[f][0]+=dp[u][0];dp[f][1]+=dp[u][1];dp[u][0]=dp[u][1]=0; }printf("%lld\n",ans); }return 0;//拜拜程序~ } ```