本文移植自个人的原博客（原文）

题目链接

题目描述

题解

设$to$数组为给出数组的逆，$ans$为答案数组，那么对于一个$i$有两种约束条件：

$ans[i]>ans[b[i]]$
$ans[j] < i \ and \ j < a[i] and \ j!=i)$

此处可以利用查分约束，将关系用边表示然后进行拓扑排序，但遍历所有关系的时间复杂度为$O(n^2)$,无法通过极限数据。可以考虑用线段树进行优化，将第二种关系用线段树进行查询，并模拟原题中的$mark$操作，在遍历后从线段树中删除该点，期望时间复杂度$O(nlogn)$。

#include<bits/stdc++.h>
#define y second
using namespace std;
typedef long long ll;
const int N = 1e6+1;
const int inf = 0x7fffffff;

int n,a[N],head[N],cnt,d[N],to[N];
bool vis[N];
pair<int,int>q;
struct nd{int ne,to;}e[N*50];

struct segment_tree
{
    pair<int,int>t[N];

    void update(int x){t[x]=max(t[x<<1],t[x<<1|1]);}

    void build(int x,int l,int r)
    {
        if(l==r){t[x]=make_pair(to[l],l);return;}
        int mid=l+r>>1;
        build(x<<1,l,mid);build(x<<1|1,mid+1,r);
        update(x);
        return;
    }

    pair<int,int> query(int x,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R)return t[x];
        int mid=l+r>>1;
        pair<int,int> ret=make_pair(0,0);
        if(L<=mid)    ret=max(ret,query(x<<1,l,mid,L,R));
        if(R>mid)    ret=max(ret,query(x<<1|1,mid+1,r,L,R));
        return ret;
    }

    void delet(int x,int l,int r,int d)
    {
        if(l==r){t[x]=make_pair(0,l);return;}
        int mid=l+r>>1;
        if(d<=mid)    delet(x<<1,l,mid,d);
        else        delet(x<<1|1,mid+1,r,d);
        update(x);
        return;
    }

}T;
int tot;
int dfs(int x)
{
    vis[x]=1;
    T.delet(1,1,n,x);
    if(to[x]!=n+1&&!vis[to[x]])dfs(to[x]);
    if(a[x]>1)
    while(1)
    {
        pair<int,int> v=T.query(1,1,n,1,a[x]-1);
        if(v.first>x)dfs(v.second);
        else    break;
    }
    d[x]=++tot;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1;i<=n;++i)
    if(a[i]!=-1)    to[a[i]]=i;
    else    a[i]=n+1;
    for(int i=1;i<=n;++i)if(!to[i])to[i]=n+1;
    T.build(1,1,n);
    for(int i=1;i<=n;++i)if(!vis[i])dfs(i);
    for(int i=1;i<=n;++i)printf("%d ",d[i]);
}

Codeforces798E Mike and Code of a Permutation

题目链接

题目描述

题解