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

pekempeyのブログ

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

CodeChef May Challgenge 2016: Easy Queries

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

問題

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

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

解法概要

D-Query 永続 + wavelet matrix。

  • 計算量 O(n log2 n)
  • 空間計算量 O(n log2 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 を構築する。

f:id:pekempey:20160515215418p:plain

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

f:id:pekempey:20160515215527p:plain

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

CodeChef May Challgenge 2016: Easy Queries

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