CF1158C

题意:有排列p, 令\(nxt_i\)为\(p_i\)右侧第一个大于\(p_i\)的数的位置，若不存在则\(nxt_i=n+1\)

现在整个p和nxt的一部分丢失了，请根据剩余的nxt，构造出一个符合情况的p，输出任意一解。

使有解的充要条件是对于每一个i不存在\(j\in(i,nex_i)\)满足\(nex_j>nex_i\)

也就是说对于每个\(i\)向\(nxt_i\)连一条边，然后没有两条边相交

对于点\(i\)向\(nex_i\)和满足\(j<i \ \wedge nex_j>nex_i\)的最小的j连边

这样的话就是一个拓扑图

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#define M 2100001

#define N 500010

using namespace std;

int n,m,k,a[N],d[M],s[N],ver[N],t[N],T,B;

queue<int> q;

void ins(int now,int l,int r,int k,int x)

{

	if(l==r)

	{

		d[now]=k;

		return;

	}

	int mid=(l+r)>>1;

	if(x<=mid) ins(now*2,l,mid,k,x);

	else ins(now*2+1,mid+1,r,k,x);

	d[now]=1;

}

int ask(int now,int l,int r,int L)

{

	if(l==r) return d[now];

	int mid=(l+r)>>1, k=0;

	if(L<=mid && d[now*2]) k=ask(now*2,l,mid,L);

	if(!k)return ask(now*2+1,mid+1,r,L);

	return k;

}

void rb(int now,int l,int r)

{

	if(!d[now]) return ;

	d[now]=0;

	if(l==r) return ;

	int mid=(l+r)>>1;

	rb(now*2,l,mid);

	rb(now*2+1,mid+1,r);

}

int main()

{

	scanf("%d",&T);

	for(T;T;T--)

	{

		B=0;

		scanf("%d",&n);

		for(int i=1;i<=n;i++)

		{

			scanf("%d",&a[i]);

			if(a[i]==-1) a[i]=i+1;

		}

		for(int i=1;i<=n;i++)

		{

			k=ask(1,1,n+1,i+1);

			if(k && a[k]<a[i])

			{

				B=1;

				break;

			}

			ins(1,1,n+1,i,a[i]);

			s[a[i]]++;

			if(!k) continue;

			ver[i]=k; s[k]++;

		}

		if(!B)

		{

			for(int i=1;i<=n;i++) if(!s[i]) q.push(i);

			k=0;

			while(q.size())

			{

				int x=q.front(); q.pop();

				s[ver[x]]--; s[a[x]]--;

				if(!s[ver[x]]) q.push(ver[x]);

				if(!s[a[x]]) q.push(a[x]);

				t[x]=++k;

			}

			if(k!=n+1) B=1;

		}

		if(B) printf("-1");

		else for(int i=1;i<=n;i++) printf("%d ",t[i]);

		printf("\n");

		for(int i=1;i<=n+1;i++) t[i]=s[i]=ver[i]=a[i]=0;

		rb(1,1,n+1);

	}

}

巴特西

CF1158C

最新文章

热门文章