https://atcoder.jp/contests/arc183/tasks

A

分类讨论奇偶，看样例基本上能猜出来。

B

  • 注意 $K=1$ 是容易判断的。

  • 第二种情况是 $b_i$ 出现了 $a_i$ 没出现的数字。

否则 $K \geq 2$，以及 $a_i$ 里面有所有 $b_i$ 出现的值。

考虑最后一步如果能弄出来 $b$，那么 $b$ 肯定有两个相同数字的距离小于等于 $K$，并且有相同的数字。

验证这是充要条件：考虑除了最后一步全都使用 $k=2$ 的操作，这样就可以类似插入排序来做，假设相同的数字是 $(i, j)$ 拿其中某一个相同的数字，比如说 $i$，可以当做一个中间值，也就是 temp 的作用，也就是除了最后一个位置都能达成。

只需要满足最后一步的条件即可。

C

考虑 $bad_{l,r,i}$ 表示 $[l,r]$ 中的最大值不能是 $i$ 这个位置。

然后类似笛卡尔树分治下去求方案即可。

记忆化搜索。

D

考虑这个其实最开始是给了一个合法的方案。

然后找到一个重心。

重心有如下性质：

  • 可以一一配对，并且配对的答案更大。

  • 一棵树最多有两个重心。

  • 重心最大的儿子 $\frac{n}{2}$

然后考虑这个重心的配对方案，最开始是到 $v_1$ 这一棵子树，然后如果选择一个 $v1$ 中的叶子和 $v_2$ 的叶子，对链进行调整之后，重心的配对方案会到 $v2$ 的这棵子树，也就是每次做迭代即可，直到删完。