[AtCoder][ABC174F] 数字の配列における指定の範囲にある数字の種類を数える

次の問題の解答を解説する。
ABC174 F - Range Set Query

問題

下記配列Aがあり、指定の範囲(l, r)にある数字の種類を答える。

i: 0 1 2 3 4 5 6 7 8 9
A: 2 5 6 5 2 1 7 9 7 2

考え方

配列の各数字における1つ前に発生した数字のインデクスをPとする。
初めて発生した数字には-1を記録する。

i:  0  1  2 3 4  5  6  7 8 9
A:  2  5  6 5 2  1  7  9 7 2
P: -1 -1 -1 1 0 -1 -1 -1 6 4

ここでインデクスiと配列Pに注目する。
指定の範囲(l, r)に(i, P[i])が含まれていればその数字は重複しているとわかる。

数字A[i]が範囲(l, r)内で重複しているかの判断： l <= i && P[i] <= r

よって答えは下記を計算すればよい。

l - r + 1 - (重複数)

重複数の計算の仕方

(i, P[i])を2次元平面上にプロットする。
すると範囲(l, r)内にある重複数というのは下記の黄色の範囲となる。
この範囲に存在する(i, P[i])の数を効率よく数え上げる。

数え上げのコツとしてはまず(l, r)と(i, P[i])を全てプロットしておく。
そしてiの大きい方から座標を評価していき、(l, r)に当たったらそれまでに発見した座標の中でrより小さいP[i]を数え上げることで回答できる。
数え上げにはBITを利用すると効率よく計算できる。