← 返回题目列表

AtCoder · yahoo_procon2017_final_c

C. 倍数kueri

中文机器翻译题面 查看原题

配点 : 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

每题之后的数列值如下。

  • 第一题之后,数列是 [3, 4, 4, 3, 4] 变成.
  • 在第二个问题之后,数列为 [3, 4, 4, 3, 4] 变成.
  • 在第三个问题之后,数列为 [3, 4, 4, 8, 9] 变成.
  • 在第四个问题之后,数列为 [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