题解 AT1984 【[AGC001F] Wide Swap】

小粉兔

2020-06-07 05:11:58

Solution

在博客园食用更佳:[https://www.cnblogs.com/PinkRabbit/p/AGC001F.html](https://www.cnblogs.com/PinkRabbit/p/AGC001F.html)。 ### 题意简述 有一个 $1 \sim N$ 的排列 $P_1 \sim P_N$,你可以执行如下操作任意多次: - 选取两个下标 $i, j$($1 \le i < j \le N$),还需满足 $j - i \ge K$ 且 $|P_i - P_j| = 1$,然后交换 $P_i$ 与 $P_j$ 的值。 请问你能得到的字典序最小的排列是什么?请输出它。 - $1 \le N \le 5 \times {10}^5$。 ### 题解 它给了个排列 $P$,然后 $i, j$ 两个位置能交换的条件是 $|i - j| \ge K$ 并且 $|P_i - P_j| = 1$。 这个条件看起来十分的玄妙,考虑 $Q$ 为 $P$ 的逆置换,那么此时就相当于如果 $|Q_i - Q_{i + 1}| \ge K$ 你就可以交换位置 $i$ 和 $(i + 1)$。 看起来舒服多了。我们需要求出字典序最小的 $P$,放到 $Q$ 上就是要让**值**为 $1$ 的**下标**尽量靠前($Q_x = 1$ 的 $x$ 尽量小),以此类推。 然后再考虑 $Q$ 中的两个值,如果它们的差小于 $K$,那么它们就永远无法交换,也就是顺序就被定死了。 也就是说:对于所有满足 $|u - v| < K$ 的 $(u, v)$,它们在 $Q$ 中出现的相对位置被固定了。 而对于两个排列 $Q, R$,我们可以证明如果每一对 $(u, v)$ 在 $Q, R$ 中的相对位置都相同的话,它们就可以互相转换。限于篇幅不证。 也就是说只要求出满足所有 $(u, v)$ 限制的排列即可。再次回到初始排列 $P$,重写限制为: 对于所有满足 $|i - j| < K$ 的下标 $(i, j)$,如果初始时 $P_i < P_j$,则最终的排列也必须有 $P_i < P_j$,反之亦然。 你可以回去观察一下样例是否满足这个条件,一定是满足的。 然而此时我们需要让 $P_1$ 尽量小,在此条件下让 $P_2$ 尽量小,以此类推。 可以发现我们把不等号写出来后,整个序列就变成了个 DAG,我们要给予每个点适当的拓扑编号,让拓扑编号的字典序尽量小。 这就变成了一个经典问题。**在一般情况下**,它的解决方案**并不是**部分题解所述的:「直接拓扑排序,但每次优先取编号最小的点」。 **而是**:把所有边反向,然后拓扑排序(也就是倒着拓扑排序),但每次优先取编号最大的点,拓扑编号也从 $N$ 往 $1$ 编号。 这两种方法是对称的,但是**在一般情况下**求得的东西并不相同,且第二种才是对的。 无论如何,这张图的边数还是 $\mathcal O (N K)$ 的,不能显式建图做。我们考虑用数据结构优化这个过程: 任意时刻下,入度为 $0$ 的点,即是满足 $P_i$ 为在 $(i - K, i + K)$ 中(注意是开区间)的最大值的 $i$。 删除一个点 $i$ 就相当于把 $P_i$ 改成 $-\infty$,与此同时会影响到周围 $(i - K, i + K)$ 这个区域(开区间)的连边情况。 那么我们可以用线段树维护这个过程,初始时先查一遍每个点是否入度为 $0$,如果是就加入一个大根堆中。 然后每次取出堆顶,删除它然后分别查询 $(i - K, i)$ 和 $(i, i + K)$ 这两个区域中的最大值编号,检查是否入度为 $0$ 入堆。 最后直接输出编号即可,很有趣的一题,时间复杂度为 $\mathcal O (N \log N)$。 **最后**:之所以前文中第一种「错误」的方法也能 AC,是因为本题中特殊的连边形式: 考虑第一种方法第一次错误编号时:假设是把本应给位置 $k$ 的编号给了位置 $j$,根据算法流程,此时有 $j < k$。 现在 $j$ 的编号减小了,但答案却错了,必是因为 $k$ 的编号增大直接或间接导致了某个位置 $i$ 的编号不得不增大。此时有 $i < j < k$。 注意到此时 $j$ 是无入度的位置中最小的,所以比 $j$ 小的位置中如果还有未标号的,一定有 $j$ 向其的连边,这是因为: 一直沿 DAG 中的边往回走(删除已编号的点),最终会走到没有入度的点,如果不是 $j$ 则中间一定跨过 $j$,那时直接到 $j$ 即可。 所以一定有:最终答案中,此时未编号的,比 $j$ 小的位置,其编号一定大于 $j$ 的编号。 所以此时我们如果直接把 $j$ 的编号提到 $k$ 的编号之前,是完全不影响 $j$ 之前的所有点的编号的。 与 $i$ 的标号会增大矛盾,Q.E.D. ```cpp #include <cstdio> #include <algorithm> #include <queue> const int Inf = 0x3f3f3f3f; const int MN = 500005, MS = 1 << 20 | 7; int N, K, P[MN], Ans[MN]; #define li (i << 1) #define ri (li | 1) #define mid ((l + r) >> 1) #define ls li, l, mid #define rs ri, mid + 1, r int mxp[MS]; void Build(int i, int l, int r) { if (l == r) return mxp[i] = l, void(); Build(ls), Build(rs); mxp[i] = P[mxp[li]] > P[mxp[ri]] ? mxp[li] : mxp[ri]; } void Del(int i, int l, int r, int p) { if (l == r) return mxp[i] = 0, void(); p <= mid ? Del(ls, p) : Del(rs, p); mxp[i] = P[mxp[li]] > P[mxp[ri]] ? mxp[li] : mxp[ri]; } int Qur(int i, int l, int r, int a, int b) { if (r < a || b < l) return 0; if (a <= l && r <= b) return mxp[i]; int v1 = Qur(ls, a, b), v2 = Qur(rs, a, b); return P[v1] > P[v2] ? v1 : v2; } int inq[MN]; std::priority_queue<int> pq; inline void check(int id) { if (inq[id]) return ; if (Qur(1, 1, N, id - K + 1, id + K - 1) == id) pq.push(id), inq[id] = 1; } int main() { scanf("%d%d", &N, &K); for (int i = 1; i <= N; ++i) scanf("%d", &P[i]); P[0] = -Inf; Build(1, 1, N); for (int i = 1; i <= N; ++i) check(i); for (int i = N; i >= 1; --i) { int u = pq.top(); pq.pop(); Ans[u] = i; Del(1, 1, N, u); int pos; if ((pos = Qur(1, 1, N, u - K + 1, u - 1))) check(pos); if ((pos = Qur(1, 1, N, u + 1, u + K - 1))) check(pos); } for (int i = 1; i <= N; ++i) printf("%d\n", Ans[i]); return 0; } ```