[??记录]AT1984 [AGC001F] Wide Swap
command_block
2021-04-22 07:50:49
**题意** ： 给出一个长度为 $n$ 的排列 $p$ 。
当 $i,j$ 满足 $|i-j|\geq k$ 且 $|p_i-p_j|=1$ 时，可以交换 $p_i,p_j$。
求通过若干次上述操作能得到的字典序最小的排列。
$n\leq 5\times10^5$ ，时限$\texttt{5s}$。
------------
考虑 $p$ 的逆排列 $q$ ，则交换条件变为 ： $|q_i-q_j|\geq k$ 且 $i,j$ 相邻即可交换 $q_i,q_j$。
对于一对 $q_i,q_j$ ，若 $|q_i-q_j|<k$ ，则两者的相对顺序是固定的，否则可以任意变动。
于是，若 $q_i$ 一定要在 $q_j$ 前面，则连边 $i\rightarrow j$。
这张有向图的每种拓扑序都是一个能够造出的排列。
逆排列和原排列的字典序关系比较复杂，我们不妨直接在原排列上建图。
对于一对 $p_i,p_j$ ，若 $|i-j|<k$ ，则要求 $p_i,p_j$ 的大小关系不变。
若要求 $p_i<p_j$ ，则连边 $i\rightarrow j$。
这张有向图的每种拓扑序都是一个能够造出的排列。现在要使得 $p_1$ 尽量小，在此基础上使得 $p_2$ 尽量小……
- $\text{sub ploblem}$ : [P3243 [HNOI2015]菜肴制作](https://www.luogu.com.cn/problem/P3243)
兔队告诉我们，直接在拓扑排序的同时贪心取编号最小的点扩展是错的，应该使用下面的算法 ：
建立反图，在反图上拓扑排序，并从 $N$ 到 $1$ 编号，每次贪心取最大的编号扩展。
该算法的正确性依赖于“**字典拓扑原理**” ：
> 感谢 yhx 的指导
- 对于任意一个 ${\bf DAG}\ G$ 和 $G$ 的一个拓扑序 $p$ ： $p$ 是字典序最大的，当且仅当 $p^{-1}$ 是字典序最大的。
（若将“大”改为“小”，则命题不一定成立）
在第一个算法中，我们每次贪心地取编号最小的点，即使得 $p^{-1}$ 的字典序最小，但 $p$ 的字典序不一定最小。
在第二个算法中，我们将图的边集翻转，问题变为求出字典序最大的 $p$ ，于是等效于求出字典序最大的 $p^{-1}$ ，则可以贪心。
本题中， DAG 的边数达到 $O(nk)$ ，不能直接暴力建边。
点 $i$ 连向的点的集合为 $\{j:|i-j|<k,p_j<p_i\}$ ，故点 $i$ 入度为 $0$ 的充要条件是在 $[i-k,i+k]$ 内 $p_i$ 为最大值。
用大根堆维护目前入度为 $0$ 的点的集合。
使用线段树维护区间最大值，当删除点 $i$ 时，查询 $[i-k,i),(i,i+k]$ 中的最大值编号，并查看这两个编号是否入度变为 $0$。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define MaxN 500500
using namespace std;
Pr a[MaxN<<2];
inline void up(int u)
{a[u]=max(a[u<<1],a[u<<1|1]);}
int n,x[MaxN];
void build(int l=1,int r=n,int u=1)
{
if (l==r){a[u]=mp(x[l],l);return ;}
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
up(u);
}
int to;
void del(int l=1,int r=n,int u=1)
{
if (l==r){a[u]=mp(0,0);return ;}
int mid=(l+r)>>1;
if (to<=mid)del(l,mid,u<<1);
else del(mid+1,r,u<<1|1);
up(u);
}
int wfl,wfr;Pr ret;
void qry(int l=1,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr){ret=max(ret,a[u]);return ;}
int mid=(l+r)>>1;
if (wfl<=mid)qry(l,mid,u<<1);
if (mid<wfr)qry(mid+1,r,u<<1|1);
}
priority_queue<int> q;
int k,ans[MaxN];
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&x[i]);
build();
for (int i=1;i<=n;i++){
wfl=max(1,i-k+1);wfr=min(n,i+k-1);
ret=mp(0,0);qry();
if (ret.sec==i)q.push(i);
}
int tim=n;
while(!q.empty()){
int u=q.top();q.pop();
ans[u]=tim--;
to=u;del();
wfl=max(1,u-k+1);wfr=u-1;
if (wfl<=wfr){
ret=mp(0,0);qry();
int i=ret.sec;
if (i){
int i=ret.sec;
wfl=max(1,i-k+1);wfr=min(n,i+k-1);
ret=mp(0,0);qry();
if (ret.sec==i)q.push(i);
}
}
wfl=u+1;wfr=min(n,u+k-1);
if (wfl<=wfr){
ret=mp(0,0);qry();
int i=ret.sec;
if (i){
wfl=max(1,i-k+1);wfr=min(n,i+k-1);
ret=mp(0,0);qry();
if (ret.sec==i)q.push(i);
}
}
}
for (int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}
```