CF798E,dfs拓扑排序,线段树维护

CF798E Mike and code of a permutation

讲一下自己看solution时的障碍.

题面:

对于一个排列 (P=[p_1,p_2,dots,p_n])

定义它的编码(A)为：对于每个 (i)，找到第一个未被标记过的位置 (j) 满足 (p_j>p_i)，令 (a_i=j)，并给(j)打上标记；若没有合法的，则 (a_i=-1)。

现给出一个编码 (A)（除$ -1 $外各不相同），请输出一个合法的 (P)。

题解

我们令(b_i)表示谁选了(i),拼命观察可知

性质一:(p_{b_i}<p_i)

性质二:(forall jin[1,a_i-1]),如果(j eq i)且(b_j>i),那么(p_j<p_i)

利用这两条性质建拓扑图跑一遍,性质一递归遍历,性质二线段树维护一下

然后分配编号就好了(详见代码)

注意

这里用到了(dfs)写法的拓扑排序,先记录拓扑序大的点(即(p_i)小的点)

code

//需要注意的点:大小关系对应的是要求的数组 
#include<bits/stdc++.h>
using namespace std;
const int N=505000;
int n,a[N],b[N];
//a[i]表示i标记了谁,b[i]=a^(-1)(i)表示i被谁标记 
#define pr pair<int,int>
#define mk make_pair
#define fi first
#define se second
pr t[N<<2];
#define lson p<<1
#define rson p<<1|1
void build(int p,int l,int r){
	if(l==r){
		t[p]=mk(b[l],l);
		return;
	}
	int mid=(l+r)>>1;
	build(lson,l,mid),build(rson,mid+1,r);
	t[p]=max(t[lson],t[rson]);//pair自带比较函数 
}
void update(int p,int l,int r,int pos){
	if(l==r){
		t[p]=mk(0,l);
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)update(lson,l,mid,pos);
	else update(rson,mid+1,r,pos);
	t[p]=max(t[lson],t[rson]);
}
pr query(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R)return t[p];
	int mid=(l+r)>>1;
	if(R<=mid)return query(lson,l,mid,L,R);
	else if(L>mid)return query(rson,mid+1,r,L,R);
	else return max(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R)); 
}
int tot,l[N],p[N];//跑反图
bool vis[N];
void dfs(int u){
	vis[u]=1;
	update(1,1,n,u);//删除拓扑图上这个点 
	if(b[u]!=n+1&&!vis[b[u]])dfs(b[u]);//p[u]>p[b[u]]
	if(a[u]>1){
		while(true){
			pr now=query(1,1,n,1,a[u]-1);
			if(now.fi>u&&!vis[now.se])dfs(now.se);//取max后比较 
			else break;
			//从大往小走 
		}
	}
	l[++tot]=u;//注意p[i]最小的在第一个 
}//O(nlog(n))
int main(){
//	freopen("t.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if(a[i]!=-1)b[a[i]]=i;
		else a[i]=n+1;
	}
	for(int i=1;i<=n;++i)
		if(!b[i])b[i]=n+1;//这样定义方便线段树操作
	build(1,1,n);
	for(int i=1;i<=n;++i)
		if(!vis[i])dfs(i);
	tot=0;
	for(int i=1;i<=n;++i)p[l[i]]=++tot;
	for(int i=1;i<=n;++i)printf("%d ",p[i]);
	return 0;
}