CodeChef May Challgenge 2016: Easy Queries

https://www.codechef.com/MAY16/problems/DISTNUM2

問題

整数列 An が与えられる。A[l..r] から重複要素を無視して k 番目に小さい値を出力するというクエリを Q 個処理せよ。

• 1≦n≦10⁵
• 1≦Q≦10⁵
• オンラインクエリ

解法概要

D-Query 永続 + wavelet matrix。

• 計算量 O(n log² n)
• 空間計算量 O(n log² n)

D-Query 永続とは？

僕が勝手に名前をつけたテクニック。D-Query という問題の解法に由来する。
http://www.spoj.com/problems/DQUERY/

問題は至ってシンプルで、A[l..r] に含まれる値の個数を unique に数えるというもの。

具体的な解法は Codeforces の以下のブログで説明されている。
http://codeforces.com/blog/entry/8962

ブログではクエリをソートしているが、永続を使えばソートは不要である。具体的には、i 番目の要素までを考慮した状態を永続で持っておけばいい。

重複を無視したいとき全般に使える手法。

Wavelet Matrix とは？

色々奥が深そうなデータ構造。以下のスライドに簡潔にまとめられている。どことなく Trie っぽい。
http://www.slideshare.net/pfi/ss-15916040

今回使うのは quantile という操作。これは A[l..r] で k 番目に小さい値を返すというもの。

解法

重複要素を無視して quantile をすればいいのだから、D-Query 永続と wavelet matrix を組み合わせればいい。

wavelet matrix からある要素を無かったことにするのは簡単である。たとえば次のような wavelet matrix を構築する。

0001 を無かったことにするには、wavelet matrix 上で 0001 が辿る要素をすべてなかったことにすればいい（実際にはセグ木の値を 0 にするだけ）。

17*17*2*10⁵≒60000000 ノード必要なので MLE が心配だが大丈夫らしい。

CodeChef May Challgenge 2016: Easy Queries

「k 番目　クエリ」と検索をかけたら 「G番目の数字」の解説 を見つけて wavelet matrix というものを知った。 割と有名なデータ構造なのか説明しているサイトが多く助かった。