【题解】牛客练习赛97

本场比赛视频讲解：https://www.bilibili.com/video/BV1Kb4y1s7Xj

A

这道题一种容易的写法是，将整个序列排序后，判断每个位置的奇偶性是否与原来相同。

B

首先有个套路做法，注意到 和 均只会变化 次，暴力抠出来就行，复杂度 。

可是我们很容易就发现选一个数是最优的，关于这部分的证明我的想法是把所有数扔到 trie 树上贪心证明，不过感性理解这个结论应该也不难。所以只需要输出二倍的最大值即可。复杂度 。

C

我们假设我们最大化走冰之格的答案，火之格同理。

我们可以发现，每个格子只会被反转一次时，每个格子反转后的答案的差值是可以确定。

我们假设不反转格子，走冰之格的情况，显然我们只会走那些 为正数的格子。

那么考虑翻一个冰之格 对答案的差值，如果 ，那么我们在一开始就没有选定他，答案只会减 去翻格子的代价 。否则，我们一开始是选定他的 ，翻转后的贡献的差值是 。

再考虑翻一个火之格 对答案的差值，如果 那么即使翻过来也不会去走这个格子翻转后贡献差值是 ，否则我们翻过来必然会走这个格子，贡献差值是 。

这样我们就算完了所有的翻转后的贡献差值了，只要将最大的 个贡献为正的翻转加到答案里就行。

时间复杂度 。

D

可以直接树形 dp， 表示染特殊颜色或普通颜色的方案数。

转移是简单的：

E

（非常抱歉，出题人赛前并没有发现牛客多校存在一道跟这题几乎一样的题，并且由于后面更改了数据范围的原因，最后一版数据造弱了，导致有一个乱搞做法过了，非常非常抱歉。）

我们发现这个问题等价于任意选两堆石子将其石子数 （关于这个结论的证明可以调整）。

这就是个很经典的结论了 并且 为偶数。

如何去统计这样的区间数呢？

先预处理 。

我们按从上到下递减建出笛卡尔树，设当前区间是 ，最大值位置为 。那么相当于最大值为 的区间左端点 满足 ，右端点 满足 。

一个很暴力的想法，枚举右端点 ，相当于查询 满足 且 。因为前缀和 是递增的，直接 lower_bound 即可，极限情况下复杂度 。

更进一步，我们又可以利用类似启发式合并的想法，枚举 这两个区间中的较小者，复杂度即可做到 。

F

由于查询时每次取出到根路径上美丽程度最大的点并一直暴力摘钻石的复杂度总和是 的，所以问题转化为了树上加点，将某个点的钻石清除，查询到根节点路径上有钻石的美丽程度最大的点。

考虑树分块，记块大小为 。

开始只有树根单独一个块。加入一个新节点时，检查其父亲块的大小是否达到 ，若达到则新建一个块，令新节点作为块的根，否则将当前节点并入父亲的块。

可以发现这样能满足每个块中都是一个大小不超过 的联通块。

对于块内每个点，维护其到块根的路径上美丽程度最大的节点的美丽程度和编号。

查询时一直暴力跳块根，即可求出查询节点到根路径上美丽程度最大的点。由于除了深度最高的块其它的块大小一定是 ，所以复杂度

清除钻石时，暴力更新块内所有节点维护的信息即可，时间复杂度 。

取 时最优。实际因为常数原因调整一下会更优。

最后复杂度 。

P.S. 利用 LCT 可以直接做到单 log 的复杂度。

G

为了方便，我们现在让查找算法返回 而不是 。

容易观察到，如果查找到了一个位置 ，其判定次数是固定的，我们记为 。

枚举位置 ，并计算查找到位置 的序列数量，就可以得到答案：
直接暴力实现就是 的。

仔细想想暴力计算的式子基本不可做，所以我们换个方向。

发现对 进行差分后，不为 的位置显然只有 个。

此时问题变为计算查找到位置 后的序列数量。显然可以枚举位置 的取值 ，得到：

发现后面那个和式在 增加 时只会增加一项，于是可以暴力维护。

时间复杂度 。