CF1158C Permutation recovery 做题记录

有排列 pp,令 nxtinxt_ipip_i 右侧第一个大于 pip_i 的数的位置,若不存在则 nxti=n+1nxt_i=n+1

现在整个 ppnxtnxt 的一部分丢失了,请根据剩余的 nxtnxt,构造出一个符合情况的 pp,输出任意一解。

1n5×1051\le n\le 5\times 10^5

O(n)O(n) 单调栈+递归构造即可,完全不需要线段树优化建图跑拓扑。

首先发现由于 nxti=min{jj>i,pj>pj}nxt_i=\min\{j|j>i,p_j>p_j\},所以 a[i,nxti1]a_{[i,nxt_i-1]} 都要比 anxtia_{nxt_i} 小,nxt[i,nxti1]nxt_{[i,nxt_i-1]} 也都要小于等于 nxtinxt_i。设 firi=min{jnxtj=i}fir_i=\min\{j|nxt_j=i\},那么不难发现 firi,ifir_i,i 构成了类似括号匹配的关系:

那么扫一遍序列,用单调栈找到最内层的“右括号”的位置 pospos,刚开始单调栈中只有一个元素 n+1n+1。扫到位置 ii 时:

  • 先将单调栈顶小于等于 ii 的元素弹出;
  • nxti=1nxt_i=-1,那么让 nxtiposnxt_i\to pos
  • 否则:
    • nxti>posnxt_i>pos,那么无解;
    • 否则若 nxti=posnxt_i\not= pos 那么把 nxtinxt_i 加入单调栈;

可以通过下面的构造 pp 序列的方法证明这样构造 nxtnxt 是正确的:

不难发现,由于括号的嵌套关系,所以内层小段的构造方法和外层大段的基本相同,只需要加上一个偏移量即可,所以考虑递归构造。

dfs(l,r,mov)dfs(l,r,mov) 表示构造在括号 lftnxtr,nxtrlft_{nxt_r},nxt_r 中的 p[l,r]p_{[l,r]} 这一段,并且整一段的偏移量为 movmov

显然边界条件是 nxt[l,r]=nxtrnxt_{[l,r]}=nxt_r,这时只要构造 {rl+1+mov,rl+mov,rl1+mov,,2+mov,1+mov}\{r-l+1+mov,r-l+mov,r-l-1+mov,\dots,2+mov,1+mov\} 这样倒着的序列即可。

由于某个 “右括号” 也有可能是左括号,这时这两段要看作一段处理。所以先预处理出 lbilb_i 表示以 ii 为右端点的“连通块”的左端点:

注意若 ii 不为“左括号”或者“右括号”,那么 lbi=ilb_i=i

dfs(l,r,mov)dfs(l,r,mov) 中:

  1. 初始化一个空队列 vecvec,令 pmov=movpmov=mov
  2. 从右往左扫过区间,扫到 ii 时:
    • nxti=nxtrnxt_i=nxt_r,说明 pip_i 属于最外层的括号,那么把 ii 放入队列 vecvec 的末尾,最后再处理;
    • nxti=nxtrnxt_i\not=nxt_r,说明 pip_i 属于内层的某个括号中,那么递归处理 dfs(lbi,i,pmov)dfs(lb_i,i,pmov),令 ilbi1i\to lb_i-1pmovpmov+ilbi+1pmov\to pmov+i-lb_i+1
  3. 队列 vecvec 中的元素 ii 都满足 nxti=nxtrnxt_i=nxt_r,并且队列中元素是从大到小排列的。那么参照 nxt[l,r]=nxtrnxt_{[l,r]}=nxt_r 情况的构造方法,不断从队头取出元素 ii,令 pipmovp_i\to pmovpmovpmov+1pmov\to pmov+1 即可。

代码如下:

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=500005;

int n,nxt[S];
int sta[S];
int lb[S],a[S];

void dfs(int l,int r,int mov)
{
	int len=r-l+1,nxmov=mov;
	vector<int> vec;
	for(int i=r;i>=l;i--)
	{
		if(nxt[i]!=nxt[r]) dfs(lb[i],i,nxmov),nxmov+=i-lb[i]+1,i=lb[i];
		else vec.push_back(i);
	}
	for(int u:vec) a[u]=++nxmov;
}

inline void slove()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&nxt[i]);
	int top=1;
	sta[1]=n+1;
	for(int i=1;i<=n;i++)
	{
		while(sta[top]<=i) top--;
		if(nxt[i]==-1) nxt[i]=sta[top];
		else
		{
			if(nxt[i]>sta[top])
			{
				puts("-1");
				return;
			}
			else if(nxt[i]<sta[top]) sta[++top]=nxt[i];
		}
	}
	for(int i=1;i<=n;i++) lb[i]=i;
	for(int i=1;i<=n;i++) lb[nxt[i]]=min(lb[nxt[i]],lb[i]);
	dfs(1,n,0);
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	printf("\n");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}