赛时想写 60pts，结果 cxr 似乎少算了一点空间，导致我一直没把空间卡过去QWQ。
当时不会 dfs 求拓扑序，这里讲一下。
枚举所有非访问过的点依次 dfs，每次进行下列操作：
-
找出 \(v\) 的一个未访问过的入点 \(u\)，调用
dfs(u)； -
找不到 \(u\) 的时候，把 \(v\) 加入拓扑序列中。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+10;
int n,a[N],p[N];
pair<int,int>t[N<<2];
void pushup(int rt){
t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
void build(int l=1,int r=n,int rt=1){
if(l==r){
t[rt]={p[l],l};
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void erase(int x,int l=1,int r=n,int rt=1){
if(l==r){
t[rt]={-1,l};
return;
}
int mid=(l+r)>>1;
if(x<=mid)erase(x,l,mid,rt<<1);
else erase(x,mid+1,r,rt<<1|1);
pushup(rt);
}
pair<int,int> query(int L,int R,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1;
pair<int,int>s(-1,0);
if(L<=mid)s=max(s,query(L,R,l,mid,rt<<1));
if(mid<R)s=max(s,query(L,R,mid+1,r,rt<<1|1));
return s;
}
int cnt,ans[N];
void dfs(int i){
if(ans[i])return;
erase(i);
if(p[i]<=n)dfs(p[i]);
for(;a[i]>1;){
auto x=query(1,a[i]-1);
if(x.first<=i)break;
dfs(x.second);
}
ans[i]=++cnt;
}
int main(){
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
fill(p+1,p+1+n,n+1);
for(int i=1;i<=n;i++)
if(~a[i])p[a[i]]=i;
else a[i]=n+1;
build();
for(int i=1;i<=n;i++)dfs(i);
for(int i=1;i<=n;i++)printf("%d%c",ans[i],"\n "[i<n]);
return 0;
}