ABC248_D – Range Count Query

問題
提出
1. 解けた

問題

D - Range Count Query

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #44806753 - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解けた

公式解説とほとんど同じ。
$A_i$の数列->どの数字がどこで出現したか、に置き換える。
入力例1の場合、以下のようになる。
$1: [2,4]$
$2: []$
$3: [1]$
$4: [3]$
$5: [5]$

これで$X$が何番目に出現したかがわかる。
$[L,R]$の間に何個数字があるかを計算するために二分探索をする。
$L$は含むのでL以上になる場所を求める。
これにはc++のlower_boundが使える。
$R$も含むのでRより大きい場所を求める必要がある。
これにはc++のupper_boundが使える。
これらの差分で個数がわかる。
計算量は$O(Qlog(N))$になる。