https://atcoder.jp/contests/abc203/submissions/23082310
- 小さい数を-1、大きい数を+1、としてカウントすると線形処理で中央値かどうか判別可能
中央値を求めるデータ構造として2個の priority_queue を持つ のアルゴリズムがあり、スライドウィンドウして処理したくなる。しかし、この問題では数値に重複がある上に削除も必要なので priority_queue が使えず代わりに multiset などを使うと find に線形時間かかるためTLEしてしまう。
結論から言うと、小さい数を-1、大きい数を+1、でカウントして中央値を求める方針が正解（唐突）。何も工夫しなければ線形時間かかるが、二次元累積和を使えば矩形毎に で判別できる。中央値Aについて-1と+1のカウント数に単調性があるため二分探索できる。以上から二分探索しながら毎回二次元累積和を構築しても
で意外と高速に求まることが分かる。
感想: スライドウィンドウの解法が脳裏に浮かんで無限時間かけて実装してしまった
