← 返回题目列表

Codeforces · 316/E3

E3. 暑假作业

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

聪明海狸三岁时就掌握了所有算术运算,并从惊奇的老师那里得到了今年暑假作业:

给定一个整数序列 a1, a2, ..., an。您的任务是对其执行以下类型的 m 个连续操作:

1. 对于给定的数字 xi 和 vi,将值 vi 赋给元素 axi。
2. 对于给定的数字 li 和 ri,您必须计算总和 $$\sum_{x=0}^{r_i-l_i} (f_x \cdot a_{l_i+x})$$,其中 f0 = f1 = 1 且 i ≥ 2: fi = fi - 1 + fi - 2。
3. 对于一组三个数字 li ri di,您应该对所有 x 将 ax 值增加 di (li ≤ x ≤ ri)。

聪明海狸计划了一次加拿大大湖之旅,所以他请求你帮助他解决给定的问题。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2·105) — 相应地,序列中整数的数量和操作的数量。第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 105)。然后是m行,每行描述一个操作。每行以一个整数 ti (1 ≤ ti ≤ 3) 开始——操作类型:

- 如果 ti = 1,则接下来跟随两个整数 xi vi (1 ≤ xi ≤ n, 0 ≤ vi ≤ 105);
- 如果 ti = 2,则接下来是两个整数 li ri (1 ≤ li ≤ ri ≤ n);
- 如果 ti = 3,则接下来跟随三个整数 li ri di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 105)。

得分 30 分的输入限制为(子问题 E1):

- 保证n不超过100,m不超过10000,并且不会有第3类查询。

得分 70 分的输入限制为(子问题 E1+E2):

- 保证仅存在第一和第二类型的查询。

获得 100 分的输入限制为(子问题 E1+E2+E3):

- 没有额外的限制。

输出

对于每个查询,打印计算出的总和模 1000000000 (109)。

示例

输入 #1

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

输出 #1

12
32
8
50

输入 #2

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

输出 #2

12
45