本文主要是介绍Codeforces Round #410 (Div. 2) E. Mike and code of a permutation（拓扑序+线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：http://codeforces.com/contest/798/problem/E
题解：
大力补了一发E，看了半天的官方题解，结合了它的代码才看懂。。。还是菜啊？
首先很容易考虑到，可以通过拓扑序的方式来构造出答案，那么如何建图就成了问题的关键。
如果ai==-1，则让ai=n+1，如果某个点没有比它小的节点，就把它连到n+1
然后可以通过遍历一个有向图，每次遍历到某个边，就将该边删除。
考虑边（i，j）表示pi>pj，那么，在区间【1，a[i]-1】（i为当前节点）中的任意点j，如果存在边（j，k）且k>i，则必有pi>pj，如果不存在，那么表示已经不存在比点pi小的节点。
可以通过反证法给予证明：
考虑区间【1，a[i]-1】存边（j，k）其中，1<=j<=a[i]-1，1<=k<now，且pi>pj，因为我们是从1遍历到i，如果该边存在，那么一定有j>i，因为从i连出去的边我们会第一个遍历，否则这条边我们一定已经遍历过，那么考虑a[k]，因为a[k]!=i，那么一定有pm>pk，而且m<k，在这种情况下，a[k]=m<i，所以不存在。
所以问题就转换成了，求一个区间中的最大值，同时支持修改区间中的某个点的模型。可以通过一个线段树来维护，每个点表示这个区间中的点连接的点集中，编号最大的点是那一个，并且维护该边的编号。删除操作只需要把该点连接到0就好。
时间复杂度O（nlogn）
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
using namespace std;
const int MAXN=5e5+5;
pair<int,int> tree[MAXN<<2];
int a[MAXN],b[MAXN],ans[MAXN];
bool book[MAXN];
int n;
vector<int> sv;
void push_up(int rt)
{tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
void build(int l,int r,int rt)
{if(l==r){tree[rt]=mp(b[l],l);return ;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);push_up(rt);
}
void update(int pos,int val,int l,int r,int rt)
{if(l==r){tree[rt]=mp(val,tree[rt].yy);return ;}int mid=(l+r)>>1;if(pos<=mid){update(pos,val,l,mid,rt<<1);}else{update(pos,val,mid+1,r,rt<<1|1);}push_up(rt);
}
pair<int,int> query(int L,int R,int l,int r,int rt)
{pair<int,int> ret;if(L>R){return mp(0,0);}if(L<=l&&r<=R){return tree[rt];}int mid=(l+r)>>1;if(L<=mid){ret=max(ret,query(L,R,l,mid,rt<<1));}if(R>mid){ret=max(ret,query(L,R,mid+1,r,rt<<1|1));}return ret;
}
void dfs(int now)
{book[now]=true;update(now,0,1,n,1);if(b[now]!=n+1&&!book[b[now]]){dfs(b[now]);}while(1){pair<int,int> mx=query(1,a[now]-1,1,n,1);if(mx.xx>now){dfs(mx.yy);}else{break;}}sv.push_back(now);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){b[i]=n+1;}for(int i=1;i<=n;i++){if(a[i]!=-1)b[a[i]]=i;}for(int i=1;i<=n;i++){if(a[i]==-1)a[i]=n+1;}build(1,n,1);for(int i=1;i<=n;i++){if(!book[i])dfs(i);}for(int i=0;i<sv.size();i++){ans[sv[i]]=i+1;}for(int i=1;i<=n;i++){printf("%d ",ans[i]);}printf("\n");return 0;
}这篇关于Codeforces Round #410 (Div. 2) E. Mike and code of a permutation（拓扑序+线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
