AT_nikkei2019_2_qual_c 题解

blog。不会做结论题，怎么办？？？不会做结论题，怎么办？？？不会做结论题，怎么办？？？

不妨对 \(b\) 排序，将 \(a\) 对应到相应的位置。那么题目有两个条件：

• #1：\(\forall a_i\le b_i\)。
• #2：操作限制。

注意到 \(n-1\) 次操作就能完成对 \(a\) 排序。所以用 \(n-2\) 次操作可以将 \(a\) 变成一个 Almost Sorted 的状态。

启示我们对 \(a\) 排序（下文记为 \(a^\prime\)）并直接进行分讨。具体地：

• 若 \(\exists a^\prime_i>b_i\)，由 #1，不会存在一个合法的 \(a\)，NO。
• 否则，若 \(\exists a^\prime_{i+1}\le b_i\)，此时有 \(a^\prime_i\le a^\prime_{i+1}\le b_i\le b_{i+1}\)，交换 \(a^\prime_i,a^\prime_{i+1}\) 后仍满足 #1 且满足 #2，YES。
• 否则，交换任一 \(a^\prime_i,a^\prime_j\) 后序列都不满足 #1，即合法的 \(a\) 必须有序。直接检验 \(a^\prime\) 是否满足 #2 即可。

code，时间复杂度 \(O(n\log n)\)。