C - 倍数クエリ
Editorial
/
Time Limit: 6 sec / Memory Limit: 512 MB
配点 : 1000 点
問題文
高橋君は,数列 [A_1, A_2, ..., A_N] を持っています. 高橋君は,数列のある区間内の数すべてに同じ値を足すのが好きです.また,高橋君は M の倍数が好きなので,数列のある区間に現れる M の倍数の個数が気になります.
高橋君のために,次のような質問に答えてあげてください.ただし,質問は全部で Q 個与えられるものとします.
- i 番目の質問では,l_i, r_i, d_i が与えられる.まず,A_{l_i}, A_{l_i + 1}, ..., A_{r_i} それぞれの値に d_i を足す.その後,A_{l_i}, A_{l_i + 1}, ..., A_{r_i} の中にある M の倍数の個数を答える.
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq l_i \leq r_i \leq N
- 0 \leq d_i \leq 10^9
- A_i, d_i は整数
入力
入力は以下の形式で標準入力から与えられる.
N M Q A_1 A_2 ... A_N l_1 r_1 d_1 l_2 r_2 d_2 : l_Q r_Q d_Q
出力
i 行目には,i 番目の質問に対する答えを出力せよ.
入力例 1
5 4 4 1 2 4 3 4 1 2 2 2 5 0 4 5 5 1 5 3
出力例 1
1 3 1 1
各質問の後での数列の値は以下のようになります.
- 1 番目の質問の後,数列は [3, 4, 4, 3, 4] になる.
- 2 番目の質問の後,数列は [3, 4, 4, 3, 4] になる.
- 3 番目の質問の後,数列は [3, 4, 4, 8, 9] になる.
- 4 番目の質問の後,数列は [6, 7, 7, 11, 12] になる.
入力例 2
10 7 9 6 10 6 10 3 8 1 8 7 2 1 9 6 3 4 9 8 9 6 3 6 3 1 9 9 1 3 7 2 6 2 1 10 0 8 9 4
出力例 2
3 1 0 1 3 1 2 4 0