首页 > 其他分享 >「CF798E」 Mike and code of a permutation

「CF798E」 Mike and code of a permutation

时间:2023-02-17 20:45:25浏览次数:39  
标签:连边 Mike code 标记 拓扑 CF798E define

\(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

相关文章