← 返回题目列表

Codeforces · 1136/E

E. 娜斯蒂亚还没有写下传奇

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

在这个任务中,Nastya 要求我们写一份正式的声明。

给出了长度为 $$$n$$$ 的数组 $$$a$$$ 和长度为 $$$n-1$$$ 的数组 $$$k$$$。应处理两种类型的查询:

- 将 $$$a_i$$$ 增加 $$$x$$$。那么如果 $$$a_{i+1} < a_i + k_i$$$,则 $$$a_{i+1}$$$ 恰好变为 $$$a_i + k_i$$$;再次,如果 $$$a_{i+2} < a_{i+1} + k_{i+1}$$$,则 $$$a_{i+2}$$$ 恰好变为 $$$a_{i+1} + k_{i+1}$$$,到目前为止,对于 $$$a_{i+3}$$$,...,$$$a_n$$$;
- 打印数组 $$$a$$$ 中从第 $$$l$$$ 个元素到第 $$$r$$$ 个元素的连续子数组的总和。

保证最初 $$$a_i + k_i \leq a_{i+1}$$$ 对于所有 $$$1 \leq i \leq n-1$$$ 。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^{5}$$$) — 数组 $$$a$$$ 中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leq a_i \leq 10^{9}$$$) — 数组 $$$a$$$ 的元素。

第三行包含 $$$n-1$$$ 整数 $$$k_1, k_2, \ldots, k_{n-1}$$$ ($$$-10^{6} \leq k_i \leq 10^{6}$$$) — 数组 $$$k$$$ 的元素。

第四行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$) — 查询数。

以下 $$$q$$$ 行中的每一行都包含两种类型之一的查询:

- 如果查询是第一种类型,则对应行包含字符 '+' (不带引号),然后有两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq x \leq 10^{6}$$$),表示将整数 $$$x$$$ 添加到$$$i$$$ - 数组 $$$a$$$ 的第一个元素,如语句中所述。
- 如果查询具有第二种类型,则相应行包含字符 's'(不带引号),然后有两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$)。

输出

对于第二种类型的每个查询,在新行中打印一个整数 - 相应子数组的总和。

示例

输入 #1

3
1 2 3
1 -1
5
s 2 3
+ 1 2
s 1 2
+ 3 1
s 2 3

输出 #1

5
7
8

输入 #2

3
3 6 7
3 1
3
+ 1 3
+ 2 4
s 1 3

输出 #2

33

注意

在第一个示例中:

- 第一次更改后 $$$a = [3, 4, 3]$$$;
- 第二次更改后 $$$a = [3, 4, 4]$$$。

在第二个示例中:

- 第一次更改后 $$$a = [6, 9, 10]$$$;
- 第二次更改后 $$$a = [6, 13, 14]$$$。