Codeforces #404 E. Anton and Permutation

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

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

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

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

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

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