Vasya has written some permutation 𝑝1,𝑝2,…,𝑝𝑛 of integers from 1 to 𝑛, so for all 1≤𝑖≤𝑛 it is true that 1≤𝑝𝑖≤𝑛 and all 𝑝1,𝑝2,…,𝑝𝑛 are different. After that he wrote 𝑛 numbers 𝑛𝑒𝑥𝑡1,𝑛𝑒𝑥𝑡2,…,𝑛𝑒𝑥𝑡𝑛. The number 𝑛𝑒𝑥𝑡𝑖 is equal to the minimal index 𝑖<𝑗≤𝑛, such that 𝑝𝑗>𝑝𝑖. If there is no such 𝑗 let's let's define as 𝑛𝑒𝑥𝑡𝑖=𝑛+1.

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values 𝑛𝑒𝑥𝑡𝑖 are completely lost! If for some 𝑖 the value 𝑛𝑒𝑥𝑡𝑖 is lost, let's say that 𝑛𝑒𝑥𝑡𝑖=−1.

You are given numbers 𝑛𝑒𝑥𝑡1,𝑛𝑒𝑥𝑡2,…,𝑛𝑒𝑥𝑡𝑛 (maybe some of them are equal to −1). Help Vasya to find such permutation 𝑝1,𝑝2,…,𝑝𝑛 of integers from 1 to 𝑛, that he can write it to the notebook and all numbers 𝑛𝑒𝑥𝑡𝑖, which are not equal to −1, will be correct.

大致题意 📖

有排列pp, 令nxtinxt_i ,为 pip_i 右侧第一个大于pip_i的数的位置,若不存在则 nxti=n+1nxt_i=n+1
现在整个ppnxtnxt的一部分丢失了,请根据剩余的nxtnxt,构造出一个符合情况的pp,输出任意一解。

链接 🔗

「CodeForces 1158C」Permutation recovery

题解 ❓

拓扑排序 + 线段树优化建图

代码

const int N = 2e6+10;
ll a[N],ls[N],rs[N],tot,id[N],rt,d[N],ans[N],n,num;
V G[N];
void build(ll &p,ll l,ll r)
{
    p = ++tot; a[p] =  d[p] = 0; G[p].clear();
    if(l==r)
    {
        a[p] = l, id[l] = p;
        return;
    }
    build(ls[p],l,mid);
    build(rs[p],mid+1,r);
    G[p].pb(ls[p]); G[p].pb(rs[p]);
    d[ls[p]]++;d[rs[p]]++;
}
ll change(ll p,ll l,ll r,ll x,ll y,ll v)
{
    if(x > y) return 0;
    if(x <= l && r <= y) return G[v].pb(p),d[p]++;
    if(x <= mid) change(ls[p],l,mid,x,y,v);
    if(y > mid) change(rs[p],mid+1,r,x,y,v);
}
int main()
{
//    __IN;__OUT;
    ll t;RLL(t);
    while(t--)
    {
        RLL(n); tot = 0; num = n;
        build(rt,1,n);
        FOR(i,1,n)
        {
            ll x;RLL(x);
            if(x!=-1)
            {
                if(i+1 <= x-1) change(rt,1,n,i+1,x-1,id[i]);
                if(x <= n)
                    G[id[x]].pb(id[i]),d[id[i]]++;
            }
        }
        queue<ll> que;

        FOR(i,1,tot) if(!d[i])que.push(i);
        while(!que.empty())
        {
            ll x = que.front(); que.pop();
            if(a[x]) ans[a[x]] = num--;
            for(auto v:G[x])
            {
                --d[v];
                if(!d[v]) que.push(v);
            }
        }
        if(num) PS("-1");
        else
        {
            FOR(i,1,n) PLP(ans[i]);
            PN();
        }
    }
    return 0;
}