Codeforces Round 915 (Div. 2) 题解

A.Constructive Problems

直接找规律，或者手玩一下发现按照对角线斜着放最优（不会证），答案即为 $max(n, m)$ 。

每次我们选择的端点一定是叶子结点，最优性是显然的。因为每次可以删掉两个叶子，设叶子数为 $p$，答案即为 $ \left\lceil \dfrac{p}{2} \right\rceil $。

发现我们选中的字典序最大的子序列内的元素不会变，只会按照题目要求循环移动。（如果会变，那么它在最开始就应该被选入子序列中。）

显然，这个子序列的字典序是单调不升的，想要排好序，就要把除了最大的字母以外的其他字母全部移到前面去，设子序列长度为 $len$，最大的字母出现了 $k$ 次，答案即为 $len - k$。

但是，不在子序列里的字母也会影响是否能成功排序，所以最后可以暴力 check 一下移动后是否排好序，没排好就说明无解。

参考 HDU-4747，很像。

几乎完全一致的做法。把原本顺序的 mex 都求出来，考虑把第一个数放到最后面产生什么影响。

因为是一个环状的东西，考虑复制一遍拼在后面，方便处理。

假设当前这个数是第 $i$ 个数，它被放到 $i + n$ 的位置上。那么 $i + n$ 位置上的 mex 显然和原本第 $n$ 个位置上的 mex 相等，单点修改即可。

而删掉第 $i$ 个数，产生的影响就是在区间 $[i + 1, i + n - 1]$ 内，mex 大于 $a_i$ 的位置全部变成 $a_i$，由于 mex 的前缀单调性，我们可以直接线段树二分找出要操作的区间，区间赋值即可。

对于每次的答案，询问 $[i, i + n - 1]$ 的 mex 之和，取个最小值即可。

综上，我们需要一个支持区间查和、最大值，区间复制的线段树，直接维护即可。

以上为场切。

评价：写题太慢还一直挂，多练。