pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces #404 E. Anton and Permutation

http://codeforces.com/contest/785/problem/E

解法

  • 区間[l,r]にある x 以上(以下)の要素の個数を求める
  • i 番目の要素の値を書き換える

という操作のできるデータ構造があれば解くことができるのは分かる。

書き換え操作がなければ、セグメント木で解くことができる。しかし、書き換えをするとなると、セグメント木に平衡二分木を載せる必要がでてきて、実装量が多くなってしまう。

セグメント木ではなく平方分割で書けばいい。

本番では LLRB という赤黒木の一種を使って解いた。

http://codeforces.com/contest/785/submission/25528555

treap だと TLE すると思ったが、ちょっと書き換えたら通った。

http://codeforces.com/contest/785/submission/25530899

AVL木で書いたのも速かった。さほどinsert操作を呼ばないからかな。

http://codeforces.com/contest/785/submission/25572561