很好的题

/*
nexti:pi右边第一个比pi大的数的下标
把每个[i,a[i]]都看成一段区间,区间只能在端点处交叉,以此来判断是否有解
特别的,如果a[i]=-1,那么把a[i]=i+1,不对其他区间造成任何影响
如何判区间合法性:用一个set记录区间右边界,每次遍历到左端点i时将set里的i删去,然后放入右边界a[i],同时进行判断
如何输出解 :从n+1开始,右端点向左端点连边,然后拓扑排序(bfs)即可
*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 500005
int n,a[maxn],t,ans[maxn];
vector<int>G[maxn]; int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=;i<=n+;i++)G[i].clear();
set<int>s;
int flag=; for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++){
if(a[i]==-)a[i]=i+;
while(s.find(i)!=s.end())
s.erase(i);
if(!s.empty() && *s.begin()<a[i])flag=;
s.insert(a[i]);
G[a[i]].push_back(i);
} if(flag){puts("-1");continue;}
int id=n;
queue<int>q;q.push(n+); while(!q.empty()){
int u=q.front();q.pop();
for(int i=;i<G[u].size();i++){
int v=G[u][i];
ans[v]=id--;
q.push(v);
}
}
for(int i=;i<=n;i++)cout<<ans[i]<<" ";
puts("");
}
}

最新文章

  1. Struts2中的ModelDriven机制及其运用
  2. plsql11.06注册码
  3. JS-字符串操作-替换
  4. 搜索栏会消失 uisearchbar 狂点消失的问题解决
  5. EasyUI 后台接受DataGrid传来的参数
  6. 详解Spring事件驱动模型
  7. 【jmeter】元件的作用域与执行顺序
  8. centos下 rpm包sphinx安装成功提示
  9. AIX性能监控topas命令的详细解析
  10. BootStrap2学习日记13----关于按钮
  11. 原生JS研究:学习jquery源码,收集整理常用JS函数
  12. ASF(传感器)
  13. RNN的介绍
  14. ConvertUtils.register注册转换器
  15. 3200 [HNOI2009]有趣的数列
  16. contos mysql 删除
  17. Struts学习资料
  18. 2018.11.04 NOIP训练 小水塘(并查集)
  19. python测试开发django-25.表单提交之post注册案例
  20. WPF中的命令与命令绑定导航

热门文章

  1. Pathfinding 模板题 /// BFS oj21413
  2. 【python】collections的使用
  3. websokect的原理
  4. Linux-iptables-route-rule
  5. XSS攻击原理
  6. CSIC_716_20191113【装饰器进阶以及迭代器】
  7. sublime text-----查看当前文件的编码格式
  8. 概率dp的迭代方式小结——zoj3329,hdu4089,hdu4035
  9. python 毫秒时间戳转日期
  10. error C2712: Cannot use __try in functions that require object unwinding