题解：P11845 [USACO25FEB] Min Max Subarrays P

cike_bilibili · 2026-11-11 16:28:35 · 题解

首先由于这个操作是和次数奇偶相关的，先考虑对区间长度的奇偶性分讨一下。

首先是奇数，我们有结论，当区间长度 \ge 5 时，答案为其区间最大值。考虑证明，考虑最大值的位置，其左右两边一定有一边有 \ge 2 个位置，先将较短的一边缩成一个，然后如果接下来的操作是 \max 就缩掉，否则就在另一边操作一下再过来缩掉，这样最大值一定被放在了边上，从另一边开始依次合并即可剩下这个最大值。

而对于长度为 3 的区间我们有简单的反例 1 2 1，第一次一定会把中间的合并了。

然后是偶数，我们又有结论，当长度 \ge 8 时，区间答案一定是次大值，依旧考虑证明，考虑最大两个值的位置，将区间分为三段，一定有一段 \ge 2，如果这一段 \ge 3，我们就可以将其他两段缩成单点过后用这一段调整，否则三段长度均为 2，也就是 00100100，我们依旧可以给出一组构造。而对于 n=6，我们可以给出一个反例 121121 第一次一定缩掉 11，那么第三次一定会干掉一个 2。

于是问题分为三个部分，len \le 6，奇数，偶数。

第一个部分随便写一个状压或者搜索就好了。

奇数部分维护单调栈即可。

偶数部分，考虑将 \sum_i if_i 拆成 \sum_i f_{\ge i} 的形式，从小到大枚举值，维护合法区间个数，这个可以用链表维护。

我们认为那个 6 的区间长度是一个常数，时间复杂度 O(n)。

代码有点丑不放了。