题解：CF2126G2 Big Wins! (hard version)

· · 题解

首先使用单调栈求出每一个数 a_i 作为最小值的的区间 [l_i,r_i]。

考虑如何判定一个区间的中位数是否大于等于 v：将小于 v 的数映射为 -1，大于等于 v 的数映射为 1，区间和大于等于 0 即代表着该区间的中位数大于等于 v。

即对于区间 [l_i,r_i]，[l_i,i-1] 的最大后缀和加上区间 [i+1,r_i] 的最大前缀和，再加上 i 位置对应的值大于等于 0 就代表着在区间 [l_i,r_i] 内存在包含 i 的子区间使得其中位数大于等于 v。类似于最大子段和使用线段树维护即可。

这样就有了一个 O(n \log^2 n) 做法：使用主席树维护出 v=1,2,3,\cdots, n 时所对应的线段树，每次 v 增大即为将序列中的若干个数从 1 单点修改为 -1。然后枚举每一个数 a_i，二分 v，判断 [l_i,r_i] 是否满足上述条件即可。

考虑到要求的答案为中位数减最小值，在最小值增大时，中位数也要增大才会变得更优，所以我们可以从小到大枚举每一个数，并同时维护一个数 x，代表最小值在目前从小到大枚举的数中时，中位数最大是多少。

这样，在枚举新的一个数时，我们只需要每次判断 x 能否变为 x+1，如果能，就增大 x，重复这个过程只到 x 变得尽量大，并更新答案。我们也不再需要可持久化线段树，在 x 增大 1 的时候顺便进行单点修改即可。

这样做，即使当前的数作为最小值所对应的中位数小于 $x

时间复杂度 $O(n\log n)$。