CodeTON Round 6 (Div. 2)
内容提要
本文讨论了多个编程题目，包括构造数组以达到特定的MEX值、通过位运算优化数组的异或和、在矩阵中找到特定值的最小矩形，以及在预算限制下最大化字典序的数组。每个题目都提供了解题思路和代码实现。
延伸解读
题目A的构造思路与边界条件
题目A要求构造长度为n、最大值为x、MEX为k的数组，并最大化元素和。关键边界是k > x+1或n < k时无解，因为MEX为k要求0到k-1全部出现，若k > x+1则最大值x无法覆盖k-1，若n < k则长度不足。有解时，先放置0到k-1，剩余位置尽可能取最大值x（但若x等于k，则不能取x，否则MEX会超过k，故取x-1）。这种构造保证了MEX恰好为k且和最大。
题目B中奇偶性与位运算的关联
题目B允许对数组a的每个元素反复或上数组b中的任意元素，求最终异或和的最大值和最小值。核心观察是：异或和的每一位取决于该位在a中1的个数的奇偶性。或操作可以将a中所有元素的某些位变为1，从而改变奇偶性。若a的长度为奇数，则将所有位变为1会使异或和最大（全1），不操作则最小；若长度为偶数，则将所有位变为1会使异或和最小（全0），不操作则最大。因此只需根据n的奇偶性选择是否应用b的或和。
题目C的矩形覆盖与单调性
题目C中，矩阵b的元素为min(a_i, a_j)，对于每个值x，需要找到包含所有x的最小矩形。由于b_{i,j} ≤ x当且仅当a_i ≤ x或a_j ≤ x，x出现的位置由a中≤x的元素决定。实际上，x的矩形边界由a中第一个和最后一个≤x的元素的位置决定，但更准确地说，是第一个和最后一个≥x的元素？根据题解，每个值的矩形必须包裹比它大的值的矩形，因此可以从大到小遍历，用当前值的首次和末次出现位置更新区间，确保小区间覆盖大区间。最终矩形大小为2*(right-left+1)。
题目D的贪心与单调栈优化
题目D要求在预算k内，通过选择前缀加一操作，使数组字典序最大。由于字典序优先比较靠前元素，应尽可能让第一个元素最大。首先用单调递增栈处理价格数组c，去除价格高且前缀短的无用选项。然后贪心分配预算：先最大化第一个元素，剩余预算用于后续元素，但后续元素不能超过前一个元素的值。通过计算相邻选项的价格差，逐步确定每个位置能增加的最大次数。最后根据处理后的选项覆盖范围输出每个位置的值。
Q&A
如何构造一个特定MEX值的数组？
构造一个长度为n，最大值为x，MEX为k的数组时，若k > x + 1或n < k则无解，其他情况下可以构造满足条件的数组。
如何通过位运算优化数组的异或和？
给定两个数组a和b，异或和的最大值和最小值取决于a的长度的奇偶性，奇数时选择尽可能多的b，偶数时尽可能少选。
如何在矩阵中找到特定值的最小矩形？
对于每个数字x，找到其在数组中的首次和末次出现位置，然后根据这些位置计算出包含所有出现x的最小矩形。
在预算限制下如何最大化数组的字典序？
通过贪心策略和单调递增栈处理，尽可能将预算分配给前面的元素，以最大化字典序。
构造数组时MEX值的条件是什么？
MEX值的条件是k必须小于等于x + 1且n必须大于等于k，否则无法构造满足条件的数组。
如何处理数组的异或和以获得最大值？
处理时需关注数组长度的奇偶性，奇数时尽量选择更多的b元素，偶数时则尽量不选择，以获得最大异或和。
