http://codeforces.com/contest/813/problem/E
問題概要
N個の配列Aと、ある数Kがある。
これについてオンラインで以下のクエリに答える。
同じ数字はK個までしか数えないものとして、A[L]～A[R]の数の個数を数えよ。
解法
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未満である要素の個数を数えて答える」感じに書いている。
本質的には余り変わらないが、除算が無いぶん、こちらの方が早いかも。
