有排列 ,令 为 右侧第一个大于 的数的位置,若不存在则 。
现在整个 和 的一部分丢失了,请根据剩余的 ,构造出一个符合情况的 ,输出任意一解。
。
单调栈+递归构造即可,完全不需要线段树优化建图跑拓扑。
首先发现由于 ,所以 都要比 小, 也都要小于等于 。设 ,那么不难发现 构成了类似括号匹配的关系:

那么扫一遍序列,用单调栈找到最内层的“右括号”的位置 ,刚开始单调栈中只有一个元素 。扫到位置 时:
- 先将单调栈顶小于等于 的元素弹出;
- 若 ,那么让 ;
- 否则:
- 若 ,那么无解;
- 否则若 那么把 加入单调栈;
可以通过下面的构造 序列的方法证明这样构造 是正确的:
不难发现,由于括号的嵌套关系,所以内层小段的构造方法和外层大段的基本相同,只需要加上一个偏移量即可,所以考虑递归构造。
设 表示构造在括号 中的 这一段,并且整一段的偏移量为 。
显然边界条件是 ,这时只要构造 这样倒着的序列即可。
由于某个 “右括号” 也有可能是左括号,这时这两段要看作一段处理。所以先预处理出 表示以 为右端点的“连通块”的左端点:

注意若 不为“左括号”或者“右括号”,那么 。
在 中:
- 初始化一个空队列 ,令 ;
- 从右往左扫过区间,扫到 时:
- 若 ,说明 属于最外层的括号,那么把 放入队列 的末尾,最后再处理;
- 若 ,说明 属于内层的某个括号中,那么递归处理 ,令 ,;
- 队列 中的元素 都满足 ,并且队列中元素是从大到小排列的。那么参照 情况的构造方法,不断从队头取出元素 ,令 , 即可。
代码如下:
#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;
}