はまやんはまやんはまやん

hamayanhamayan's blog

Army Creation [Educational Codeforces Round 22 E]

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

問題概要

N個の配列Aと、ある数Kがある。
これについてオンラインで以下のクエリに答える。
同じ数字はK個までしか数えないものとして、A[L]~A[R]の数の個数を数えよ。

必要知識

  • ダブリング
  • 数列のある要素の区間の中である区間の数の範囲内の要素数を数えるテク

(平方分割、セグメント木、範囲木、平衡二分木、Wavelet行列)

解法

http://codeforces.com/contest/813/submission/27684075

まず、全ての要素についてprevKを計算する。
prevK[i] := A[i]と同じ数でK個前にある要素番号(無ければ-1)
これを計算するために
pre[d][i] := A[i]と同じ数で2^d個前にある要素番号(無ければ-1)
を予め計算しておく。
あとは、ダブリングの要領でprevKも計算する。

次にクエリの答え方だが、配列prevKを使うと高速に数え上げる事ができる。
区間内の要素について含めてはいけない個数を数え上げて、全体から引く方針を考える。
i([L,R])番目の要素がK個目である条件と言うのは、L≦prevK[i]であると言える。
これはK個前の要素が範囲内にあるということだから。
なので、[L,R]の範囲でprevK[i]がL以上である要素の個数を数え上げればいい。

これはいくつかの実装方法がある

  • 平方分割
  • セグメント木(公式Editorialはこの手法が書いてある)
  • 範囲木(natsugiriさん)
  • 平衡二分木(いつだったか、pekempeyさんがこれで解いてた記憶がある)
  • Wavelet行列(antaさんの神データ構造)

これで解ける。
自分の解法では、Wavelet行列を使っている。
あと、「[L,R]の範囲でprevK[i]がL以上である要素の個数を数えて引く」のではなく「[L,R]の範囲でprevK[i]がL未満である要素の個数を数えて答える」感じに書いている。
本質的には余り変わらないが、除算が無いぶん、こちらの方が早いかも。