CF1158C Permutation recovery 做题记录

有排列 $p$，令 $nxt_i$ 为 $p_i$ 右侧第一个大于 $p_i$ 的数的位置，若不存在则 $nxt_i=n+1$。

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

$1\le n\le 5\times 10^5$。

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

首先发现由于 $nxt_i=\min\{j|j>i,p_j>p_j\}$，所以 $a_{[i,nxt_i-1]}$ 都要比 $a_{nxt_i}$ 小，$nxt_{[i,nxt_i-1]}$ 也都要小于等于 $nxt_i$。设 $fir_i=\min\{j|nxt_j=i\}$，那么不难发现 $fir_i,i$ 构成了类似括号匹配的关系：

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

• 先将单调栈顶小于等于 $i$ 的元素弹出；
• 若 $nxt_i=-1$，那么让 $nxt_i\to pos$；
• 否则：
  • 若 $nxt_i>pos$，那么无解；
  • 否则若 $nxt_i\not= pos$ 那么把 $nxt_i$ 加入单调栈；

可以通过下面的构造 $p$ 序列的方法证明这样构造 $nxt$ 是正确的：

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

设 $dfs(l,r,mov)$ 表示构造在括号 $lft_{nxt_r},nxt_r$ 中的 $p_{[l,r]}$ 这一段，并且整一段的偏移量为 $mov$。

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

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

注意若 $i$ 不为“左括号”或者“右括号”，那么 $lb_i=i$。

在 $dfs(l,r,mov)$ 中：

1. 初始化一个空队列 $vec$，令 $pmov=mov$；
2. 从右往左扫过区间，扫到 $i$ 时：
   • 若 $nxt_i=nxt_r$，说明 $p_i$ 属于最外层的括号，那么把 $i$ 放入队列 $vec$ 的末尾，最后再处理；
   • 若 $nxt_i\not=nxt_r$，说明 $p_i$ 属于内层的某个括号中，那么递归处理 $dfs(lb_i,i,pmov)$，令 $i\to lb_i-1$，$pmov\to pmov+i-lb_i+1$；
3. 队列 $vec$ 中的元素 $i$ 都满足 $nxt_i=nxt_r$，并且队列中元素是从大到小排列的。那么参照 $nxt_{[l,r]}=nxt_r$ 情况的构造方法，不断从队头取出元素 $i$，令 $p_i\to pmov$，$pmov\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;
}