题解：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$，我们也不会把答案变得更优，因为一定有之前将中位数更新到 $x$，且值小于等于当前数的一个数，答案一定不劣。

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