\(O(n^2)\)做法
让第\(i\)个点向\(p_j(p_j>p_i)\)的点连边
首先\(i\)肯定能连向\(a_i\),若当\(a_i==-1\),那么当前所有没打过标记的点向\(i\)连边,然后就可以跑出一个拓扑序来,这个拓扑序就是答案
优化
设\(b_{a_i}=i\),即\(b_x=y\)表示\(x\)是被\(y\)标记的点,如果\(x\)未被标记,那么\(b_x=n+1\)
若\(a_i==-1\),令\(a_i=n+1\)
权值小的点向大的点连线的话,也就是\(i\)向\(j\)(\(1\leq j<a_i\&\&b_j>i\))
可以先考虑如果知道了\(p\)数组求\(a\)数组所能得到的一些规律:对于所有\(1\leq j<a_i\)且未被标记的\(j\),\(p_j<p_i\)
所以\(b_j>i\)就是对应
未被标记
然后就可以\(dfs\)递归求拓扑序了,具体就是先将当前点\(x\)从序列中删除,然后若\(b_x\neq n+1\),说明\(p_{b_x}<p_x\),这时就可以继续递归\(b_x\),下一步就去找\(j\in [1,a_i)\)使得\(b_j\)最大,若这个\(b_j\leq i\),那么就可以结束了,否则递归这个\(j\),重复这个步骤,最后\(p_x=++tot\)即可
寻找和删除用线段树,总体复杂度是\(O(nlogn)\)的
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define mid (l+r>>1)
#define lson (mid<<1)
#define rson (mid<<1|1)
#define ls l,mid,lson
#define rs mid+1,r,rson
#define fi first
#define se second
using namespace std;
const int N=5e5+5;
int n,a[N],b[N];
pii tree[N<<1];
void build(int l=1,int r=n,int rt=1){
if(l==r){ tree[rt]=mp(b[l],l); return; }
build(ls),build(rs);
tree[rt]=max(tree[lson],tree[rson]);
}
void delet(int x,int l=1,int r=n,int rt=1){
if(l==r){ tree[rt]=mp(0,-1); return; }
if(x<=mid) delet(x,ls);
else delet(x,rs);
tree[rt]=max(tree[lson],tree[rson]);
}
pii ask(int a,int b,int l=1,int r=n,int rt=1){
if(a>b) return {0,-1};
if(a<=l&&r<=b) return tree[rt];
if(b<=mid) return ask(a,b,ls);
else if(mid<a) return ask(a,b,rs);
else return max(ask(a,b,ls),ask(a,b,rs));
}
int p[N],tot;
void dfs(int x){
delet(x);
if(b[x]!=n+1&&!p[b[x]]) dfs(b[x]);
for(;;){
pii t=ask(1,a[x]-1);
if(t.fi<=x) break;
dfs(t.se);
}
p[x]=++tot;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]<0) a[i]=n+1;
else b[a[i]]=i;
}
for(int i=1;i<=n;++i) if(!b[i]) b[i]=n+1;
build();
for(int i=1;i<=n;++i) if(!p[i]) dfs(i);
for(int i=1;i<=n;++i) printf("%d ",p[i]);
return 0;
}
标签:连边,Mike,code,标记,拓扑,CF798E,define
From: https://www.cnblogs.com/LuoyuSitfitw/p/17131450.html