【拓扑排序】AGC001FWide Swap

分析：

额，这是一道相当恶心的结论题。
对于给出的序列$p$，可以求得其的逆$q(p_{q_i}=i)$

并且，要使得$p$的序列字典序尽可能小，即要求$q$中1的位置尽量靠前，其次2的位置尽量靠前。。。（有些题解认为p字典序尽量小=q字典序尽量小，但我怎么都觉得不对，但至少官方题解的说法是我这样的。）

观察题目中对p的要求，再转移到q上就等价于：
在q中选择相邻的两个元素，且两元素只差不小于k，就可以交换这两个。

这样一来就有个很显然的性质了：对于任意一对$i,j$若满足$|q_j-q_i|< k$则其相对位置不可能改变。

这样一来，我们可以构造一个图，将限制条件转化为边，然后按拓扑序输出即可。

但是就这样建图会超时$n^2$条边。所以可以简化一下，对q序列的位置$i$而言，只需要连上满足$j>i$且$q_i-q_j<k(q_j<q_i)或q_j-q_i<k(q_i<q_j)$的最小的jj<script type="math/tex" id="MathJax-Element-1012">j</script>边各一条即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 500010
using namespace std;
int p[MAXN],q[MAXN];
set<int> pre,bac;
vector<int> a[MAXN];
priority_queue<int> que;
int n,k,pri[MAXN];
int vis[MAXN];
int main(){SF("%d%d",&n,&k);for(int i=1;i<=n;i++){SF("%d",&p[i]);q[p[i]]=i;}for(int i=1;i<=k;i++)bac.insert(p[i]);set<int>::iterator b,g;for(int i=1;i<=n;i++){b=bac.upper_bound(p[i]);g=pre.upper_bound(p[i]);if(b!=bac.end()){//PF("{
    %d %d}\n",q[*b],i);a[q[*b]].push_back(i);vis[i]++;}if(g!=pre.end()){//PF("[%d %d]\n",q[*g],i);a[q[*g]].push_back(i);vis[i]++;}pre.insert(p[i]);if(i-k+1>0)pre.erase(p[i-k+1]);if(i+k<=n)bac.insert(p[i+k]);bac.erase(p[i]);}for(int i=1;i<=n;i++)if(vis[i]==0)que.push(i);int tot=0;while(!que.empty()){int x=que.top();que.pop();pri[++tot]=x;//PF("[%d]",x);for(int i=0;i<a[x].size();i++){vis[a[x][i]]--;if(vis[a[x][i]]==0)que.push(a[x][i]);}}for(int i=1;i<=n;i++)q[pri[i]]=n-i+1;for(int i=1;i<=n;i++)PF("%d\n",q[i]);
}