题目传送门：https://www.nowcoder.com/acm/contest/142/J
题意：给一个hash table，求出字典序最小的插入序列，或者判断不合法。
分析：
eg.对于序列{7,8,16}，插入后为{16, -1, -1, -1, -1, -1, -1, 7, 8}。（即，依次插入7,8,16。而插入16时发现7已经被占，所以依次考虑（h(x)+1）%n ，因此16放在0的位置上。）这是正向插入，问题是给一个最终序列，问插入序列。
通过对hash表的观察可以得到：
一个区间里的数一定比单独一个数插入更早。
1.存在答案：
那么就会存在对于每一个数a[i]，存在两个位置s=a[i]%n，即本应该放在的位置。和t=i，即实际放在的位置。
朴素O（n^2）建图：
每找到一个数字s!=t，那么向前建边。若s==t，不需要建边。然后每次选择度数为0的点中最小的数（保证字典序min），然后把与该点相连的所有边删去。
通过上述朴素建图，发现每个点所建边的是一段区间内的所有点。引出：
线段树O（n）优化建图：
同上，若一个点需要连向一个区间，就向线段树上的这个区间连边。然后把度数为0的点一一删去，即把线段树内对应的叶子节点清空，然后向上更新。当一个区间为空时，就把所有连向这个点的所有边删掉了。
ps.一个点最多会向线段树上logn个区间，即logn个点相连。
2.判断不合法：
在区间[s,t)内存在-1，即序列不合法。
或拓扑排序出现环。
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
typedef pair<int,int> pii;
int fix[maxn],a[maxn];
int pos[maxn<<],id[maxn<<];
int deg[maxn<<];
vector<int> G[maxn<<];
int n;
void init(int n){
memset(deg,,sizeof(int)*(n<<|));
for (int i=;i<(n<<|);i++) G[i].clear();
}
void addedge(int u,int v){
G[u].push_back(v);
deg[v]++;
}
void build(int root,int l,int r){
id[root]=-;
if (l==r){
pos[l]=root;
id[root]=l;
return ;
}
int mid=(l+r)/;
addedge(root<<,root);
addedge(root<<|,root);
build(root<<,l,mid);
build(root<<|,mid+,r);
}
int judge(int s,int t){
if (s<=t) return (fix[t]-fix[s]==) && (a[s]!=-);
else return (fix[n-]-fix[s-]==) && !fix[t];
}
void Addedge(int L,int R,int p,int root,int l,int r){
if (L<=l && r<=R){
addedge(root,p);
return ;
}
int mid=(l+r)/;
if (L<=mid) Addedge(L,R,p,root<<,l,mid);
if (R>mid) Addedge(L,R,p,root<<|,mid+,r);
}
void topo(){
priority_queue<pii,vector<pii>,greater<pii> > Q;
for (int i=;i<n;i++)
if (!deg[pos[i]]) Q.push({a[i],pos[i]});
vector<int> ans;
while (!Q.empty()){
pii pos=Q.top();
Q.pop();
int u=pos.second;
if (pos.first!=-) ans.push_back(pos.first);
int v;
for (auto v : G[u]){
if (--deg[v]==){
if (id[v]==-) Q.push({-,v});
else Q.push({a[id[v]],v});
}
}
}
if (ans.size()!=n-fix[n-]){
cout << - << endl;
return ;
}
if (ans.size()==){
cout << endl;
return ;
}
for (int i=;i<ans.size();i++){
if (i==) cout << ans[i];
else cout << " " << ans[i];
}
cout << endl;
return ;
}
int main(){
int t;
cin >> t;
while (t--){
cin >> n;
init(n);
for (int i=;i<n;i++){
cin >> a[i];
if (i) fix[i]=fix[i-]+(a[i]==-);
else fix[i]=(a[i]==-);
}
int flag=;
for (int i=;i<n;i++){
if (a[i]!=- && !judge(a[i]%n,i)){
cout << - << endl;
flag=;
break;
}
}
if (flag) continue;
build(,,n-);
for (int i=;i<n;i++){
if (a[i]!=-){
int s=a[i]%n,t=i;
if (s==t) continue;
if (s<t){
Addedge(s,t-,pos[i],,,n-);
}
else{
if (t) Addedge(,t-,pos[i],,,n-);
Addedge(s,n-,pos[i],,,n-);
}
}
}
topo();
}
return ;
}