kazuma8128’s blog

競プロの面白い問題を解きます

CodeChef ARRQRS Logan and his ARRAY Queries

問題概要

数列に対して以下のクエリを処理せよ

  • 末尾に値 Z を追加
  • 前から X 番目の値を削除
  • 前から X 番目の値を Z に変更
  • 区間 [L, R] に含まれる値の中で小さい方から K 番目の値を出力

クエリ数 : 1e5 以下
Time Limit : 3s

解法

これらのクエリは雑に一般化すると以下になります.

  • ある位置へ値を挿入
  • ある位置の値の削除
  • ある区間の K 番目最小値の取得

これらはすべて, 動的 Wavelet Matrix でできます.
動的 Wavelet Matrix というのは, Wavelet Matrix にさらに値の挿入, 削除, 変更などができるようになった(動的になった)ものです.
やり方はシンプルで, 完備辞書に平衡二分木を使うだけです.
なので計算量は全ての操作に平衡二分木の O(logN) (Nは要素数) がさらに付きます.

というわけで, この問題は動的 Wavelet Matrix の verify にちょうどいいとおもいます.
TLがすこしゆるめ(?)なのでがんばればギリギリ通せます.
たぶんこの問題が通らないようなら大抵の問題で使い物にならないでしょう.

ちなみに, この問題の想定解はおそらく平方分割です.

ソースコード

https://www.codechef.com/viewsolution/18947173
アホみたいに長いのでリンクだけ