\(6\) 题做出来 \(3\) 题，这一次的 D 题没能复刻上一次 Round 888 Div. 3 最后几分钟 AC 的奇迹

A. Morning Sandwich

大水题，5min时间4min都在翻译题面

直接拿 \(b\) 和 \(c+h\) 进行比较分类讨论即可

单次操作时间复杂度 \(O(1)\)

B. Monsters

首先有一个特别显然、复杂度特别高的暴力思路：把所有怪物的血量和标号放到堆里，每次拿出血量最高且标号最小的怪物，血量减去 \(k\)，再插回去

但是这样做会有很多次冗余的减法操作，所以来考虑一下所有怪物都被打成了只要一刀就能干掉的情况：显然，这时所有怪物的血量都是原血量对 \(k\) 取模的值

这就好办了，一开始就对所有怪物的血量取模，然后依旧是用大根堆（考试的时候我用的 set）来做，每次取出堆顶并输出（对 \(k\) 取模的值为 \(0\) 的怪物要特判）即可

单次操作时间复杂度 \(O(n\log n)\)

C. Binary String Copying

有一个很显然的暴力（已经尽量优化了）：

对于每一组 \((l,r)\)，将排序操作后的版本插到 Trie 里面，最后统计叶子结点的个数

这样的单次操作时间复杂度是 \(O(n\times m)\)，明显过不了

那么我们考虑一下，对于一组 \((l,r)\)，能否求出一组 \((l',r')\) 使得字符串 \(s\) 中对 \(s_l\sim s_r\) 排序和对 \(s_{l'}\sim s_{r'}\) 排序后的结果 相等 呢？

由于 \(s\) 是一个 \(0/1\) 串，这就使得整个问题的讨论简单了许多：显然，若区间 \([l,r]\) 存在 前缀全 \(0\) 串 或 后缀全 \(1\)串，那么 \(l'\) 就是 \(s_l\sim s_r\) 中 第一个出现 \(1\) 的位置，\(r'\) 就是 \(s_l\sim s_r\) 中 最后一个出现 \(0\) 的位置，\([l',r']\) 也就是在保持操作结果不变的情况下的、被包含在 \([l,r]\) 内的最小区间

所以，对于每一组 \((l,r)\)，求出 \((l',r')\) 并统计即可

但是，这还不够快，因为一旦每一次操作用枚举的方式计算 \((l',r')\)，复杂度依旧是 \(O(n\times m)\)，只不过是在常数级别进行优化而已

注意到，如果 \(l\) 不变，那么无论 \(r\) 如何变化，该区间对应的 \(l'\) 也是不变的，反之亦然

所以，我们可以提前预处理对于位置 \(i\)，它作为区间左边界和右边界时所对应的 \(l'\) 和 \(r'\)，这样每一个数据的复杂度就被优化为 \(O(n+m)\)，前一个 \(n\) 为预处理，后一个 \(m\) 对应 \(m\) 次 操作

D. Array Painting

其实思路蛮简单的，但是考场上一直 WA

首先最优的选择方案就是先把序列里所有的 \(2\) 染色，因为 \(2\) 能免费把两侧的位置一起染色（要记得标记出被染的位置），完全不亏

再然后，对于序列中的 \(1\)，它们被染色后都只能把两侧其中一侧的位置一起染，所以如果出现极长的一段连续的 \(1\)，那么这一段 \(1\) 的染色费用为 \(1\)，接着还能顺便把最后一个 \(1\) 右边的位置一起染了（如果是 \(0\)，那么现在染完，之后就不用重复染这个 \(0\)；如果是 \(2\)，现在也不用染，因为之前先给所有 \(2\) 染色了）

最后剩下所有的 \(0\) 单独染色即可

E. Max to the Right of Min

考虑对于每个右端点统计答案

假设当前枚举到 \(r\) ，数组 \(a\) 满足：若区间 \([l, r]\) 满足条件，则 \(a_l=1\)，否则 \(a_l=0\)

我们考虑 \(r\) 迭代后对于数组 \(a\) 的影响，显然只有 \(p_{r+1}\) 为当前区间的最大/小值时才会对答案产生影响， 设 \(i\) 前第一个比 \(p_i\) 大的位置为 \(b_i\)，第一个比 \(p_i\) 小的位置为 \(c_i\)，\(b, c\) 容易单调栈维护求出

• 若 \(b_{r+1}<r\) (即 \(p_r<p_{r+1}\) ），则 \(p_{r+1}\) 只能当在它为最大值时造成影响，影响为: \(\forall x \in\left[b_i+1, r\right], a_x \leftarrow 1\)
• 否则 \(p_r>p_{r+1}\)，类似的，\(p_{r+1}\) 只能当在它为最小值时造成影响，影响为: \(\forall x \in\left[c_i+\right.1, r], a_x \leftarrow 0\)

然后对 \(a\) 区间更新，对于每一个 \(r\) 求出答案就可以了（每个 \(r\) 的答案就是 \(O(\log n)\) 求出的 \(l\in [1,n]\) 时的答案之和）

总复杂度 \(O(n\log n)\)

F. XOR Partition

题目的大意就是说要把一组整数分成两个集合，使得两个集合各自的 最小异或对的异或值的较小值最大

题目有点绕，但关键点就是把整数分成两个集合，不难看出这是二分图的典型用法

那么，为了让答案尽量大，我们就要让每一次抽取数对后的序列中 新的最小异或对 被 分开

套到二分图上，就是这个异或对的两个数字在二分图上连一条边，等到整个图连通以后就可以计算答案了

也就是说，我们可以假设：对于边 \((a_i,a_j)\)，其边权为 \(a_i\oplus a_j\)，那么答案就是在这张图上跑一遍最小生成树后的结果