問題 方針 単調性 判定問題 区間の中央値がX以上になる条件 区間列挙の解決策 実装 問題 長さNの数列が与えられる。この中の全ての連続部分列における中央値の中央値を求めよ。 問題へのリンク 方針 単調性 二分探索する。 中央値がX以上となる区間の数が全…

反転数とは 方針 愚直にO(N2) 高速化、O(NlogN) 方針転換 準備 実装 今回は反転数について扱っています。転倒数とも呼ばれるようです（というより競プロ界隈では転倒数の方が一般的かも？）。 問題へのリンク 反転数とは 数列があるとき、 のとき となるの組…

AOJ RSQ 問題へのリンク AOJ RSQ Binary indexed Treeによる解答 BITとは 実装 提出 Binary indexed Treeによる解答 BITとは 以下のスライドが参考になります。説明はいろいろなところにあるので、適宜調べてみてください。 Binary Indexed Tree のはなし 実…