题意简述
一个整数 $v$ 是长度为 $m$ 的数组 $b$ 的中位数，当且仅当：
- $v$ 大于等于数组中至少 $\lceil \tfrac{m}{2} \rceil$ 个元素，并且
- $v$ 小于等于数组中至少 $\lceil \tfrac{m}{2} \rceil$ 个元素。
例如：
- 数组 $[9,3,7]$ 的唯一中位数是 $7$；
- 数组 $[5,3,7,9]$ 的中位数是 $5,6,7$；
- 数组 $[2,2,2]$ 的唯一中位数是 $2$。
现在给定一个整数 $k$ 和一个数组 $a_1, \dots, a_n$，其中每个元素都是 $1$ 到 $n$ 之间的整数。
定义一个整数 $v \in [1,n]$ 为子中位数（submedian），如果存在至少一对下标 $(l,r)$ 满足：
- $1 \leq l \leq r \leq n$，
- $r - l + 1 \geq k$，
- $v$ 是子数组 $[a_l, \dots, a_r]$ 的中位数。
可以证明至少存在一个子中位数。请找出最大的子中位数 $v_{\max}$，并输出对应的一对下标 $(l,r)$。
思路分析
中位数相关，考虑二分答案。
二分出一个 $\text{mid}$，记录所有的 $a_i$ 与 $\text{mid}$ 的关系。
如果 $a_i \geq \text{mid}$，则 $b_i=1$，否则 $b_i=-1$.
那么对于一个区间 $[L, R]$，我们就可以求出 $\sum\limits_{i=L}^{R} b_i$ 的值，如果其大于等于零，就说明 $\text{mid}$ 的值大于等于这个区间的中位数。
所以 $bi$ 只要有某个区间的区间和大于等于 $\text{mid}$，即 $\max(\sum\limits{i=L}^{R}b_i) \geq \text{mid}$，那就说明 $\text{mid}$ 的值大于等于这个区间的中位数。
通过对 $b_i$ 做前缀和，我们可以记录下最小的前缀和值，然后就能求出最大的区间和。