baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ 反転数 D: Median of Medians - AtCoder Regular Contest 101 | AtCoder 問題概略 長さMの数列の任意の区間[lr]の中央値でなる数列の中央値を求めよ。 10^5 N 10^9 A解法 xが中央値が満たす条件について考えてみる。 x以上の要素がs/2以上ある。 そのような物の内最大である。上のように気づけると二分探索しようと考えることが出来る。つまり、任意の区間について中央値がx以上となるものが半分以上あれば条件を満たす。 ある区間[lr]の中央値がx以上であることを調べるには、[]をx以上なら1,その他は-1として、合計が0以上になれば良い。 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2018%2F08%2F26%2F203846" title="D - Median of Medians AtCoder Regular Contest 101 - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-08-26 20:38:46 rich https://baitop.hatenadiary.jp/entry/2018/08/26/203846 1.0 100%