题解 CF798E 【Mike and code of a permutation】

· · 题解

显然可以通过模拟编码 A 的生成得出一些位置的大小关系，如果对所有知道 p_i<p_j 的关系，从 i 向 j 连一条有向边，然后对生成的图跑拓扑排序即可得出一个合法的构造。

暴力连边空间和时间都是 \mathcal{O(n^2)} 的，观察编码 A 的生成方式发现是对于第 i 个位置，[1,a_i) 中尚未被打上标记且不等于 i 的位置会比第 i 个位置小，第 i 个位置会比第 a_i 个位置小，打上标记这个动态的操作使得优化建图不可取。

然而我们并不需要把图建出来，如果采用 dfs 来实现拓扑排序就只需要关心当前访问到的点在反图中能连到哪些点。

建立一个 b 数组， b_i 表示第 i 个点会在哪一个位置生成编码 A 时被打上标记，也就是 b_{a_i}=i ，那么对于第 i 个点，反图连向的点 j 满足 1\le j< a_i , b_j > i ,j\not= i 。

虽然连向的点是可以确定的，但是边数实际上是 \mathcal{O(n^2)} 的，所以需要用棵线段树维护可以连向的边，边做边删点，这样每次向另外一个点递归保证哪个点只会被访问一次，总复杂度为 \mathcal{O(n\log n)}

#include<bits/stdc++.h>
using namespace std;

const int M=5e5+5;

int min(int x,int y){ return x<y?x:y; }
int max(int x,int y){ return x>y?x:y; }

int n,num=0,a[M],b[M],val[M];
int read(){
    int x=0,y=1;char ch=getchar();
    while(ch<'0'||ch>'9') y=(ch=='-')?-1:1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*y;
}

namespace SegTree{
    int sum[M<<2],maxn[M<<2];
    void pushup(int u){ maxn[u]=max(maxn[u<<1],maxn[u<<1|1]); }
    void Build(int u,int l,int r){
        sum[u]=r-l+1;
        if(l==r) return (void)(maxn[u]=b[l]);
        int mid=(l+r)>>1;
        Build(u<<1,l,mid),Build(u<<1|1,mid+1,r);
        pushup(u);
    }
    void Del(int u,int l,int r,int x){
        sum[u]--;
        if(l==r) return (void)(maxn[u]=0);
        int mid=(l+r)>>1;
        if(x<=mid) Del(u<<1,l,mid,x);
        else Del(u<<1|1,mid+1,r,x);
        pushup(u);
    }
    int Find(int u,int l,int r,int L,int R,int x){
        if(l>R||r<L||!sum[u]||maxn[u]<=x||L>R) return -1;
        if(l==r) return l;
        int mid=(l+r)>>1;
        int res=Find(u<<1,l,mid,L,R,x);
        if(res==-1) res=Find(u<<1|1,mid+1,r,L,R,x);
        return res;
    }
}using namespace SegTree;

void dfs_topo(int u){
    if(!val[b[u]]&&b[u]<=n) dfs_topo(b[u]);
    int las=0;
    while(1){
        int v=Find(1,1,n,las+1,a[u]-1,u);
        if(v==-1) return (void)(Del(1,1,n,u),val[u]=++num);
        las=v;if(v==u) continue ;
        dfs_topo(v);
    }
    val[u]=++num;Del(1,1,n,u);
}

void solve(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]==-1) a[i]=n+1;
        b[a[i]]=i;
    }
    for(int i=1;i<=n;i++) if(!b[i]) b[i]=n+1;Build(1,1,n);
    for(int i=1;i<=n;i++) if(!val[i]) dfs_topo(i);
    for(int i=1;i<=n;i++) printf("%d ",val[i]);printf("\n");
}

signed main(){
    solve();
}