AGC001F Wide Swap

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 给出一个长度为 的排列 。

当 满足 且 时，可以交换 。

求通过若干次上述操作能得到的字典序最小的排列。

，时限 。

考虑 的逆排列 ，则交换条件变为： 且 相邻即可交换 。

对于一对 ，若 ，则两者的相对顺序是固定的，否则可以任意变动。

于是，若 一定要在 前面，则连边 。

这张有向图的每种拓扑序都是一个能够造出的排列。

逆排列和原排列的字典序关系比较复杂，我们不妨直接在原排列上建图。

对于一对 ，若 ，则要求 的大小关系不变。

若要求 ，则连边 。

这张有向图的每种拓扑序都是一个能够造出的排列。现在要使得 尽量小，在此基础上使得 尽量小……

兔队告诉我们，直接在拓扑排序的同时贪心取编号最小的点扩展是错的，应该使用下面的算法 ：

建立反图，在反图上拓扑排序，并从 到 编号，每次贪心取最大的编号扩展。

该算法的正确性依赖于“字典拓扑原理”：

感谢 yhx 的指导

  • 对于任意一个 和 的一个拓扑序 ： 是字典序最大的，当且仅当 是字典序最大的。

    （若将“大”改为“小”，则命题不一定成立）

在第一个算法中，我们每次贪心地取编号最小的点，即使得 的字典序最小，但 的字典序不一定最小。

在第二个算法中，我们将图的边集翻转，问题变为求出字典序最大的 ，于是等效于求出字典序最大的 ，则可以贪心。

本题中，DAG 的边数达到 ，不能直接暴力建边。

点 连向的点的集合为 ，故点 入度为 的充要条件是在 内 为最大值。

用大根堆维护目前入度为 的点的集合。

使用线段树维护区间最大值，当删除点 时，查询 中的最大值编号，并查看这两个编号是否入度变为 。

复杂度 。