問題概要
長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $があり、全ての要素は$ \ 0 \ $である。
以下のようなクエリが$ \ Q \ $回にわたって与えられる。全て処理した後の数列$ \ A \ $を求めよ。
- 約数の個数が$ \ x_i \ $以上である整数$ \ k \ (1 \leq k \leq N) \ $について、$a_k \ $の値を$ \ x_i \ $増加させる。
制約
- $1 \leq N \leq 5 \times 10^4$
- $1 \leq Q \leq 10^6$
- $1 \leq x_i \leq 10^2$
解説
$1 \ $から$ \ N \ $までの各整数の約数の個数は、$O(N \log N) \ $で求められます。
整数$ \ k \ $の約数の個数を$ \ div(k) \ $としたとき、 各整数$ \ k \ (1 \leq k \leq N) \ $について$ \ x_i \leq div(k) \ $となる$ \ x_i \ $の総和を出力すれば良いです。 この$ \ x_i \ $の総和は累積和を用いることで高速に求められます。
よってこの問題は計算量$ \ O(N \log N + Q) \ $で解くことができます。
