読者です 読者をやめる 読者になる 読者になる

insert,eraseありのk番値

スライドk番値 - sigma425のブログでsegtreeでやる方法を書いたが,kが一定の時はもっと簡単にできる.
small:小さい方からk-1個を持つ
large:それ以外を持つ
とすると,適当に増やしたり消したり移したりすればlogNで操作できる
中央値も同様にできるし1:2とかでも出来ますね.
ところでsetと書いたけどmultisetを使うべきで,eraseが難しい(erase(key)でkeyが全部消える)ので気をつけよう
昨日のD(D: ドーナツの箱詰め - Donutsプロコンチャレンジ2015 | AtCoder)
で使えたけどまあ典型なのでメモ.