好久没有单独开题目写了，主要是最近都是以补比赛为主，很少直接找题目做
但现在感觉只靠打比赛一来很难直接提升水平了，二来需要找一些知识点精进一下
所以就找了个codeforces 2100左右的graphs题，没事就刷一刷上面的题目
这题的话就比较典，首先考虑怎么判无解，如果对于\(x<y\)，满足\(x<y<nxt_x<nxt_y\)的话就一定不合法
因为根据\(y\in(x,nxt_x)\)可以知道\(p_x>p_y\)，又\(p_x<p_{nxt_x}\)，那么\(nxt_y\)不可能大于\(nxt_x\)
否则思考一下其实让所有的\(nxt_i=-1\)都有\(nxt_i=i+1\)一定不会让答案更劣，考虑此时对于一个确定的\(\{nxt_n\}\)怎么构造一组合法的解
考虑从\(n+1\)开始向前构造，对于所有\(nxt_i=n+1\)的点，显然要按照下标从小到大地给权值才行，而确定了点\(x\)的值后就可以确定所有\(nxt_y=x\)的点的权值
由于这个图的性质（每个点出边唯一且有严格的顺序），可以直接搜索求解
至于前面讲的判无解的情况其实可以先不考虑，先跑出一组解后检验下是否合法即可
总复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int t,n,p[N],a[N],idx,stk[N],top,nxt[N]; vector <int> v[N];
inline void work(CI x)
{
a[x]=idx--; for (auto y:v[x]) work(y);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n+1;++i) v[i].clear();
for (i=1;i<=n;++i) if (scanf("%d",&p[i]),~p[i]) v[p[i]].push_back(i); else v[i+1].push_back(i);
if (idx=n+1,work(n+1),idx) puts("-1"); else
{
for (stk[top=0]=n+1,i=n;i>=1;--i)
{
while (top>0&&a[stk[top]]<a[i]) --top;
nxt[i]=stk[top]; stk[++top]=i;
}
bool flag=1; for (i=1;i<=n&&flag;++i)
if (~p[i]&&nxt[i]!=p[i]) flag=0;
if (!flag) puts("-1"); else for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
}
}
return 0;
}