即给定一个长度为 \(n\) 的序列 \(\{a\}\)，求所有长度 \(\geqslant k\) 的子串中，中位数的最大值。
请记住一个套路：二分中位数答案并将原序列按与中位数的大小关系分为两部分。
sol:
在 \(a\) 的值域内二分答案 \(x\)，\(check\) 一下答案是否能大于等于 \(x\)。
因为此时我们只关心 \(a_1,a_2,a_3\dots a_n\) 和 \(x\) 的相对大小关系，所以我们可以构造一个序列 \(\{b\}\)：
\[b_i=\begin{cases} 1 & a_i\geqslant x \\ -1 & a_i<x \end{cases} \]此时序列 \(\{a\}\) 的中位数 \(\geqslant x\) 当且仅当 \(\exists l\leqslant r-k+1,\sum\limits^r_{i=l}b_i>0\)。
维护一下 \(\{b\}\) 的前缀和和前缀最小值即可 \(O(n\log n)\) AC 此题