← 返回题目列表

Codeforces · 228/D

D. 之字形

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

宫廷巫师 Zigzag 想成为一名著名的数学家。为此,他需要他自己的定理,如柯西定理,或者他的求和,如闵可夫斯基和。但最重要的是,他想要拥有他的序列(如斐波那契序列)和他的函数(如欧拉 totient 函数)。

具有 z 字形因子的 Zigag 序列是无限序列 Siz (i ≥ 1; z ≥ 2),确定如下:

- Siz = 2,当 $$( i \mod 2 ( z - 1 ) ) = 0$$ 时;
- $$S_{i}^{z} = ( i \mod 2(z-1) )$$,当 $$0 < ( i \mod 2(z-1) ) \leq z$$ 时;
- $$S_{i}^{z}=2z-(i \mod 2(z-1))$$,当 $$(i \mod 2(z-1)) > z$$ 时。

运算 $$x \mod y$$ 表示取数字 x 除以数字 y 的余数。例如,序列 Si3(之字形因子 3)的开头如下所示:1, 2, 3, 2, 1, 2, 3, 2, 1。

假设我们有一个数组 a,由 n 个整数组成。我们将数组的元素号 i (1 ≤ i ≤ n) 定义为 ai。 Zigzag 函数为函数 $$Z(l,r,z) = \sum_{i=l}^{r} a_i \cdot S_{i-l+1}^z$$,其中 l、r、z 满足不等式 1 ≤ l ≤ r ≤ n、z ≥ 2。

为了更好地熟悉 Zigzag 序列和 Zigzag 函数,向导允许您在给定数组 a 上实现以下操作。

1. 赋值操作。操作参数为(p, v)。该操作表示将值v赋给第p个数组元素。执行运算后,数组元素 ap 的值等于 v。
2.锯齿形操作。操作参数为(l, r, z)。该操作表示计算 Zigzag 函数 Z(l, r, z)。

探索之字形的神奇力量,实现所描述的操作。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 数组 a 中的元素数量。第二行包含 n 个空格分隔的整数:a1, a2, ..., an (1 ≤ ai ≤ 109) — 数组的元素。

第三行包含整数 m (1 ≤ m ≤ 105) — 操作次数。接下来的 m 行包含操作的描述。操作的描述以整数 ti (1 ≤ ti ≤ 2) — 操作类型开始。

- 如果 ti = 1(赋值操作),则该行遵循两个空格分隔的整数:pi, vi (1 ≤ pi ≤ n; 1 ≤ vi ≤ 109) — 赋值操作的参数。
- 如果 ti = 2(Zigzag 操作),则该行遵循三个空格分隔的整数:li, ri, zi (1 ≤ li ≤ ri ≤ n; 2 ≤ zi ≤ 6) — Zigzag 操作的参数。

您应该按照输入中给出的顺序执行操作。

输出

对于每个 Zigzag 操作,在一行上打印 Zigzag 函数的计算值。按输入中给出的顺序打印 Zigzag 函数的值。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

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

输出 #1

5
26
38

注意

样本测试说明:

- 第一个运算的结果是 Z(2, 3, 2) = 3·1 + 1·2 = 5。
- 第二次运算的结果是 Z(1, 5, 3) = 2·1 + 3·2 + 1·3 + 5·2 + 5·1 = 26。
- 第三次操作后数组 a 等于 2, 3, 5, 5, 5。
- 第四次运算的结果是 Z(1, 5, 3) = 2·1 + 3·2 + 5·3 + 5·2 + 5·1 = 38。