P5841 题解

· · 题解

P5841 题解

Problem Link

题目大意

给定 n 个由小写字母组成的两两不同的非空字符串 S_1,S_2,\cdots , S_n，对于一个 1 到 n 的排列 P=(p_1,p_2,\cdots,p_n)，定义 P 的价值 W(P)= \sum_{i=2}^n (\text{lcp}(S_{p_i-1},S_{p_i}))^2，设能够产生最大价值的排列为 P^*_G。

此外，还有 q 个附加任务。对于第 i 个任务，给定两个 1 到 n 之间的不同的整数 X_i 和 Y_i。对于排列 P，若 P 在满足 W(P) = W(P^*_G) 的前提条件之下，同时满足第 X_i 个字符串 S_{X_i} 恰好排在第 Y_i 个字符串 S_{Y_i} 之前， 即 \text{pos}(S_{X_i}) + 1 = \text{pos}(S_{Y_i})，其中 \text{pos}(S_i) 表示字符串 S_i 在排列中的位置，则排列 P 还将获得 2^i 的奖励。所有任务的奖励之和称之为总任务奖励。

我们设能够使得总任务奖励最大的排列为 P^*_B。

试求：

数据范围：Q\le 10^5,L=\sum |S_i|\le 2\times 10^5。

思路分析

为了防止产生前后缀关系，我们给每个 S_i 后面加上一个空字符，然后建 Trie，此时 S_i 的结尾都是不同的叶子，可以证明 P^*_G 一定是 Trie 的某个 dfs 序。

然后看附加任务，显然倒序满足最优，对于每个任务，可以看做钦定某两个点在 dfs 序中相邻。

观察发现每条限制对每个节点 u 的儿子的搜索顺序只有三种影响：钦定某个 v 为第一个或最后一个被搜的，或让某一对 v,w 连续顺次搜索。

显然用链表维护每个点儿子的搜索次序即可，更新时简单分讨一下，由于每个节点儿子数是 \mathcal O(|\Sigma|) 的，因此可以暴力合并链表。

此时瓶颈在处理路径上的每一个点，考虑优化：注意到 Trie 树上有很多出度为 1 的点，把这些点都删掉显然不影响答案。

观察简化 Trie 树的最大深度，容易发现使最大深度从 i 变成 i+1 至少需要额外插入一个长度为 i+1 的字符串，因此新 Trie 树的最大深度是 \mathcal O(\sqrt L) 的。

时间复杂度 \mathcal O(Q\sqrt L+L\times |\Sigma|^2)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
string str[MAXN];
int tot=1,edp[MAXN],tr[MAXN][27],deg[MAXN],bel[MAXN],pi[MAXN];
vector <int> G[MAXN];
int dep[MAXN],kfa[MAXN][20],fa[MAXN];
inline void init(int u,int Fa) {
    fa[u]=kfa[u][0]=Fa,dep[u]=dep[Fa]+1;
    for(int k=1;k<20;++k) kfa[u][k]=kfa[kfa[u][k-1]][k-1];
    for(int v:G[u]) init(v,u);
}
int st[MAXN],ed[MAXN]; //first and last son
int suf[MAXN],pre[MAXN],hd[MAXN],tl[MAXN],siz[MAXN]; //list<>
int lu[MAXN],lv[MAXN];
vector <int> ord;
inline void dfs(int u) {
    if(bel[u]) ord.push_back(bel[u]);
    vector <int> sons;
    for(int v:G[u]) if(hd[v]==v) sons.push_back(v);
    auto q=[&](int v) {
        if(hd[v]==st[u]) return -1;
        if(tl[v]==ed[u]) return 1;
        return 0;
    };
    sort(sons.begin(),sons.end(),[&](int x,int y) {
        return q(x)==q(y)?x<y:q(x)<q(y);
    });
    for(int v:sons) for(int i=hd[v];i;i=suf[i]) dfs(i);
}
signed main() {
    freopen("reorder.in","r",stdin);
    freopen("reorder.out","w",stdout);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    ll sum=0;
    for(int i=1;i<=n;++i) {
        cin>>str[i],str[i].push_back('z'+1);
        int p=1;
        for(int j=0;j<(int)str[i].length();++j) {
            int c=str[i][j]-'a';
            if(!tr[p][c]) {
                ++deg[p],tr[p][c]=++tot;
                if(deg[p]>=2) sum+=j*j;
            }
            p=tr[p][c];
        }
        edp[i]=p,bel[p]=i;
    }
    cout<<sum<<"\n";
    for(int i=tot;i>1;--i) {
        if(deg[i]==1) {
            for(int c=0;c<=26;++c) if(tr[i][c]) pi[i]=pi[tr[i][c]];
        } else {
            pi[i]=i;
            for(int c=0;c<=26;++c) if(tr[i][c]) G[i].push_back(pi[tr[i][c]]);
        }
    }
    for(int c=0;c<=26;++c) if(tr[1][c]) G[1].push_back(pi[tr[1][c]]);
    init(1,0);
    vector <int> lim;
    for(int i=1;i<=m;++i) cin>>lu[i]>>lv[i];
    for(int i=1;i<=tot;++i) hd[i]=tl[i]=i,siz[i]=1,pre[i]=suf[i]=st[i]=ed[i]=0;
    for(int i=m;i>=1;--i) {
        int u=edp[lu[i]],v=edp[lv[i]],x=u,y=v;
        if(dep[x]>dep[y]) {
            for(int k=19;~k;--k) if(dep[kfa[x][k]]>=dep[y]) x=kfa[x][k];
        } else {
            for(int k=19;~k;--k) if(dep[kfa[y][k]]>=dep[x]) y=kfa[y][k];
        }
        for(int k=19;~k;--k) if(kfa[x][k]^kfa[y][k]) x=kfa[x][k],y=kfa[y][k];
        int z=fa[x];
        bool ok=true;
        for(int p=u;fa[p]!=z;p=fa[p]) {
            if(ed[fa[p]]&&ed[fa[p]]!=p) ok=false;
            if(suf[p]) ok=false;
            if(st[fa[p]]==hd[p]&&siz[p]<deg[fa[p]]) ok=false;
        }
        for(int p=v;fa[p]!=z;p=fa[p]) {
            if(st[fa[p]]&&st[fa[p]]!=p) ok=false;
            if(pre[p]) ok=false;
            if(ed[fa[p]]==tl[p]&&siz[p]<deg[fa[p]]) ok=false;
        }   
        if(suf[x]!=y) {
            if(x==ed[z]||y==st[z]) ok=false;
            if(hd[x]==hd[y]) ok=false;
            if(suf[x]||pre[y]) ok=false;;
            if(hd[x]==st[z]&&tl[y]==ed[z]&&siz[x]+siz[y]<deg[z]) ok=false;
        }
        if(ok) {
            lim.push_back(i);
            for(int p=u;fa[p]!=z;p=fa[p]) ed[fa[p]]=p;
            for(int p=v;fa[p]!=z;p=fa[p]) st[fa[p]]=p;
            if(suf[x]!=y) {
                int nowh=hd[x],nowt=tl[y],nows=siz[x]+siz[y];
                suf[x]=y,pre[y]=x;
                for(int i=nowh;i;i=suf[i]) hd[i]=nowh,tl[i]=nowt,siz[i]=nows;
            }
        }
    }
    reverse(lim.begin(),lim.end());
    cout<<lim.size()<<" ";
    for(int i:lim) cout<<i<<" "; cout<<"\n";
    dfs(1);
    for(int i:ord) cout<<i<<" "; cout<<"\n";
    return 0;
}