Triple Removal Maximum Array 2

两场算法竞赛C题通关手记：

最近刷竞赛题时遇到两道很有意思的C题，分别是Triple Removal和Maximum Array 2。一道考的是前缀和加二分的区间查询技巧，另一道则是围绕MEX和区间最小值展开的构造题，琢磨透这两道题的过程里，我挖到了不少实用的解题思路，索性整理出来和大家分享。

Triple Removal：01数组的区间清空谜题

这道题的规则很有意思，给你一个只由0和1组成的数组，每次查询一个子区间，问能不能通过“移除三个相同元素”的操作把这个子区间清空。如果可以，还要算出最小的操作总成本。这里的操作成本定义得很特别，是选中的三个元素下标 i<j<k 对应的 min(k-j, j-i) 。

刚拿到题的时候，我先盯着“能不能清空”这个问题琢磨了半天。很快就发现了两个硬性条件——子数组的长度必须是3的倍数，不然连操作次数都凑不齐。再者，区间里1的总数也得是3的倍数，毕竟每次移除的三个元素要么全0要么全1，0和1的总数都得能被3整除才行。

这两个条件的判断其实不难实现。用一个前缀和数组统计前 i 个元素里1的个数，查询时只需要算一下区间内1的数量，看能不能被3整除就好。真正的难点在于怎么算最小成本。

后来我试着手动模拟了几组样例，发现了一个关键规律：如果区间里存在相邻的相同元素，那每次操作的成本都能压到1；要是区间里的元素全是交替出现的（比如0101或者1010），那每次操作的成本就得是2，对应的总费用就是 长度/3 + 1 。

基于这个规律，代码的思路就清晰了。我用一个数组 v 记录所有相邻相同元素的位置，查询区间 [l,r] 时，用二分查找判断 v 里有没有落在这个区间内的元素。如果有，总费用就是 len/3 ；没有的话，就按 len/3 + 1 来算

说句题外话，这种从样例里找规律的方法，在竞赛里真的很好用。有时候盯着题目干想半天没头绪，不如手动算几组数据，说不定规律就自己跳出来了。

Maximum Array 2：约束下的数组构造挑战

这道题的玩法完全不同，要求我们构造一个数组，满足 0 ≤ a_i ≤ 10^9 的前提下，还得搞定 q 个约束条件。约束分两种，一种是区间 [l,r] 的最小值等于 k ，另一种是区间 [l,r] 的MEX等于 k 。最终的目标是让构造出来的数组尽可能“大”，也就是每个元素的值都尽量往上限靠。

刚上手的时候，我差点被两种约束绕晕。后来仔细拆解了一下，才发现每种约束的核心要求其实很明确。

先看MEX约束，MEX是最小的未出现非负整数，所以如果一个区间的MEX是 k ，那这个区间里必须把 0 到 k-1 的数都包含进去，同时绝对不能出现 k 。而最小值约束就更直接了，区间里至少得有一个元素等于 k ，剩下的元素都不能小于 k 。

想通这两点之后，构造策略就有了。我的思路是先处理MEX约束，把 0 到 k-1 这些数先填进对应的区间里，保证MEX的要求能满足。然后再处理最小值约束，在对应的区间里放一个 k ，其余位置直接填 1e9 这种极大值，这样既能满足约束，又能让数组尽可能大。

代码实现上，我用了差分数组来标记每个位置受哪种约束影响。先通过前缀和把差分数组转换成每个位置的约束状态，再根据状态调整数组元素的值。

这里有个小坑我当时踩过——处理约束的顺序很重要。如果先处理最小值约束再处理MEX约束，很容易破坏MEX的要求，大家写代码的时候一定要注意。

其实这两道题虽然题型不同，但本质上都是“拆解约束+选对数据结构”的思路。竞赛里很多题目都是这样，看似复杂的规则背后，藏着的都是最基础的算法技巧。把核心问题抓准了，解题的思路自然就顺了。

感觉自己还是太没实力了，一年下来codefoces也只到1200～1400的水平，不知道后面的路还要不要坚持，但我相信努力终会有回报，坚持也会有回报