ながめも

競技プログラミングについて

AOJ

AOJ 反転数(転倒数)BITによる高速化

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

Binary Indexed Tree で Range Sum Query

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