https://www.codechef.com/problems/PRMQ
問題概要
N要素の配列Aがある。
これについて、Q個の以下のクエリに答える。
A[L]～A[R]を素因数分解したときに、X以上Y以下の素因数の個数を答えよ。
解法
https://www.codechef.com/viewsolution/14127309
まず、配列の各要素を素因数分解して、各素因数分解を別々に格納して、配列Bを作る。
この時、配列A[i]が配列B[l]～B[r-1]に分解されて入っていることを記録しておく。
こうすると、今回のクエリはA[L]の左端からA[R]の右端までの配列Bの中でX以上Y以下の要素の個数を数える問題となる。
これはWaveletMatrixを使うと、達成できる。
別解
セグメントツリーを使ってオフラインに解く解法もある。
naoyat.hatenablog.jp
なるほどという感じ。
これは完全永続セグメントツリーを使えば、オンラインでも解ける。
