题解：P16700 [MCO 2026] 队伍选择

· · 题解

这是某集训营 noip 模拟赛的第一题，赛时因为没有看到要让区间最长而坠机。

::::info[如果没有要求区间最长怎么办] 结论：长度为 k 的所有区间中强度的最大值就是答案。

证明：如果有一个长为 l(l > k) 的区间是答案，那么在保留其中最大值的情况下可以让区间尽可能小，因为区间长度越小，最小值是非严格单调递减的，所以长度为 k 的区间就是答案。 :::: 对于一个区间一定是有最小值的，我们可以枚举最小值 v，在满足最小值为 v 的情况下，尽可能的向左右扩展区间。

枚举编号 i，设 a_{i} 为区间的最小值，因为前后缀最小值是有单调性的，所以可以二分配合 ST 表找离 i 最近的小于 a_{i} 的数的位置，统计答案的时候判断区间长度并按题目中说的做就行了。