Codeforces Round 915 (Div. 2)
内容提要
Codeforces Round 915 Div.2 题解：A题棋盘染色最少初始格数为行列最大值；B题树压缩成点需叶子数加一除以二次；C题通过字典序最大子序列右移排序，统计操作次数并验证有序；D题循环排列使MEX前缀和最大，用线段树维护区间赋值与求和。
延伸解读
从构造到数据结构：四道题的难度递进
本场 Div.2 的题目设计呈现明显的梯度：A 题只需观察出答案等于行列最大值，属于纯构造；B 题将树压缩问题转化为叶子节点计数，需要一定的图论直觉；C 题涉及字典序最大子序列与右移操作，要求对字符串操作有清晰模拟；D 题则需用线段树维护区间赋值与求和，并理解 MEX 前缀和的变化规律。这种递进适合作为训练不同思维层次的练习。
C 题的关键：为何只需关注最大子序列
C 题的核心在于，字典序最大子序列必然是递减的，右移后最小值被移到最前，下次该位置不会再被包含。因此每次操作相当于删除子序列首尾，排序只作用于该子序列。解题时只需统计子序列长度，并检查操作后整个字符串是否有序。若最终仍存在逆序对，则输出 -1。这一思路避免了直接模拟多次操作，降低了复杂度。
D 题线段树做法的适用性与注意点
D 题利用 MEX 前缀和的性质，通过线段树维护区间赋值与求和。每次右移后，将受影响区间的贡献降低到当前最小值，并更新固定位置为 n。线段树需要支持区间取 min 和区间求和，并配合懒标记。代码中通过 ma 和 mi 判断是否完全覆盖或无需更新，实现较为高效。但需注意懒标记的传递顺序和边界处理，否则容易出错。
Q&A
Codeforces Round 915 Div.2 的 A 题最少初始染色格数怎么求？
最少初始染色格数等于棋盘行数和列数的最大值，即 max(a, b)。
B 题中把树压缩成一个点最多需要挤压几次？
最多需要挤压 (叶子结点数 + 1) / 2 次。
C 题中如何计算使字符串有序所需的最少操作次数？
先找到字典序最大的子序列，然后统计该子序列中不等于首字符的字符数量，即为操作次数；最后验证整个字符串是否有序，若有序则输出该次数，否则输出 -1。
D 题中循环排列的 MEX 前缀和最大值如何用线段树维护？
用线段树维护区间赋值与求和，初始计算每个前缀的 MEX 并更新到线段树，然后模拟右移操作，每次将当前值更新到线段树并加上固定贡献 n，同时记录最大和。
D 题中右移操作对 MEX 前缀和有什么影响？
右移后，第一个元素的 MEX 贡献被删除，从最后一个元素开始找到第一个比当前值更小的值，这期间所有值的贡献都变为当前值，再加上固定 n 的贡献。
C 题中字典序最大子序列有什么性质？
字典序最大子序列是一个递减序列，每次右移操作后，下一次得到的子序列就是上一次的子序列删掉最开头和最后面的值。
