我们把题目的过程模拟一遍，按照大小关系建图，小的向大的连边，跑一遍拓扑排序就能构造出一组合法解，但这样边数是 $\mathrm O(n^2)$ 的，不能通过。

下面给出一种拓扑排序的实现，g[i] 内存储反图的边，ans 内即为拓扑序。

void dfs(int x){
    book[x]=1;
    for(auto u:g[x])if(!book[u])dfs(u);
    ans.push_back(x);
}
void toposort(){
    for(int i=1;i<=n;i++)book[i]=0;
    ans.clear();
    for(int i=1;i<=n;i++)if(!book[i])dfs(i);
}

这种写法只需要知道哪些点可以到 $x$ 即可。

我们令 $a$ 中为 $-1$ 的位置为 $n+1$，若 $a_i\ne -1$，$b_{a_i}=i$，对于其他未赋值的 $b_i=n+1$。

则一个点 $x$ 的反边连向 $b_x$ 和所有满足 $1\le i<a_x,b_i>x$ 的 $i$。

线段树维护区间最大值，动态删点，

每个点只会被访问一次，时间复杂度 $\mathrm O(n\log n)$。

#include<cstdio>
#include<utility>
#include<algorithm>
std::pair<int,int> tr[2000010];
int n,a[500010],b[500010],v[500010];
void build(int const &x=1,int const &l=1,int const &r=n){
	if(l==r) return tr[x]=std::make_pair(b[l],l),void();
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	tr[x]=std::max(tr[ls],tr[rs]);
}
void del(int const &p,int const &x=1,int const &l=1,int const &r=n){
	if(l==r) return b[l]=0,tr[x]=std::make_pair(0,l),void();
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	if(p<=mid)del(p,ls,l,mid);
	else del(p,rs,mid+1,r); 
	tr[x]=std::max(tr[ls],tr[rs]);
}
std::pair<int,int> query(int const &p,int const &x=1,int const &l=1,int const &r=n){
	if(l==r) return tr[x];
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	if(p<=mid) return query(p,ls,l,mid);
	else return std::max(query(p,rs,mid+1,r),tr[ls]);
}
int cnt;
void dfs(int const &x){
	int k=b[x]; 
	del(x);
	if(k!=n+1&&b[k])dfs(k);
	if(a[x]!=1)
	while(1){
		std::pair<int,int> q=query(a[x]-1);
		if(q.first<=x)break;
		dfs(q.second);
	}
	v[x]=++cnt;
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		if(~a[i])b[a[i]]=i;
		else a[i]=n+1;
	}
	for(int i=1;i<=n;i++)if(!b[i])b[i]=n+1;
	build();
	for(int i=1;i<=n;i++)if(!v[i])dfs(i);
	for(int i=1;i<=n;i++)printf("%d ",v[i]);
	return 0;
}