[国家集训队] middle

中位数的性质是离不开它的排名的，所以常见的处理中位数最值的办法是二分答案。一个长为 $m$ 的序列中，（本题所定义的）中位数大于等于 $k$ 当且仅当小于 $k$ 的数的个数少于 $\left\lceil\frac m2\right\rceil$ 个。

于是这个问题就变成了，是否存在一个左端点在 $[a,b]$ 间，右端点在 $[c,d]$ 间，小于 $k$ 的数的个数少于某个与区间长度相关的值。

注意到此时限制是与区间长度相关的，难以对所有区间进行统一的处理。我们尝试对问题变形，设长为 $m$ 的区间中有 $t$ 个小于 $k$ 的数：

$$\displaylines{t<\left\lceil\frac m2\right\rceil\iff2t<m\iff(m-t)-t>0 }$$

此时式子的含义已经很明确了，中位数大于等于 $k$ 当且仅当区间中大于等于 $k$ 的数的个数减去区间中小于 $k$ 的数的个数大于 $0$。

于是可以用可持久化线段树维护，第 $i$ 个版本对应原序列中第 $i$ 小的数 $x$，线段树上某个位置小于 $x$ 赋为 $-1$，大于等于 $x$ 赋为 $1$，线段树上维护区间和、最大前缀和、最大后缀和，这样每个询问应对的所有区间的和的最大值可以通过线段树快速地求出。