← 返回题目列表

Codeforces · 438/D

D. 孩子和序列

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

六一儿童节,孩子来到皮克斯家,把家里弄得一团糟。皮克斯对他很生气。很多重要的东西都丢失了,特别是最喜欢的精选序列。

幸运的是,皮克斯记得如何修复序列。最初他应该创建一个整数数组 a[1], a[2], ..., a[n]。然后他应该执行一系列 m 操作。操作可以是以下操作之一:

1. 打印操作l, r。选择应该写下 $$\sum_{i=l}^{r}a[i]$$ 的值。
2. 模运算 l, r, x。 Picks 应该对每个 i (l ≤ i ≤ r) 执行赋值 a[i] = a[i] mod x。
3. 设置运算 k, x。 Picks 应该将 a[k] 的值设置为 x(换句话说,执行赋值 a[k] = x)。

你能帮助 Picks 执行整个操作序列吗?

输入

输入的第一行包含两个整数:n、m(1 ≤ n,m ≤ 105)。第二行包含 n 个整数,用空格分隔:a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — 数组元素的初始值。

接下来的 m 行中的每一行都以数字类型 $$(type \in \{1,2,3\})$$ 开头。

- 如果 type = 1,则该行会多出两个整数:l, r (1 ≤ l ≤ r ≤ n),对应操作 1。
- 如果type = 2,则该行会多出三个整数:l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109),对应操作2。
- 如果 type = 3,则该行会多出两个整数:k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109),对应操作 3。

输出

对于每个操作 1,请打印包含答案的行。请注意,答案可能超过 32 位整数。

示例

输入 #1

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

输出 #1

8
5

输入 #2

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

输出 #2

49
15
23
1
9

注意

考虑第一个测试用例:

- 首先,a = {1, 2, 3, 4, 5}。
- 操作 1 后,a = {1, 2, 3, 0, 1}。
- 操作 2 后,a = {1, 2, 5, 0, 1}。
- 在操作 3 中,2 + 5 + 0 + 1 = 8。
- 操作 4 后,a = {1, 2, 2, 0, 1}。
- 在操作 5 中,1 + 2 + 2 = 5。