← 返回题目列表

Codeforces · 2042/F

F. 两个子数组

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

给定两个整数数组 $$$a$$$ 和 $$$b$$$,大小均为 $$$n$$$。

让我们将子数组 $$$[l, r]$$$ 的成本定义为 $$$a_l + a_{l + 1} + \cdots + a_{r - 1} + a_r + b_l + b_r$$$。如果 $$$l=r$$$,则子数组的成本为 $$$a_l + 2 \cdot b_l$$$。

您必须执行三种类型的查询:

- "$$$1$$$ $$$p$$$ $$$x$$$" — 赋值 $$$a_{p} := x$$$;
- "$$$2$$$ $$$p$$$ $$$x$$$" — 赋值 $$$b_{p} := x$$$;
- "$$$3$$$ $$$l$$$ $$$r$$$" — 在 $$$[l, r]$$$ 段中找到两个非空非重叠子数组,总成本最大,并打印它们的总成本。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$)。

第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$)。

接下来的 $$$q$$$ 行包含查询:每行一个。每个查询属于以下三种类型之一:

- "$$$1$$$ $$$p$$$ $$$x$$$" ($$$1 \le p \le n$$$; $$$-10^9 \le x \le 10^9$$$);
- "$$$2$$$ $$$p$$$ $$$x$$$" ($$$1 \le p \le n$$$; $$$-10^9 \le x \le 10^9$$$);
- “$$$3$$$ $$$l$$$ $$$r$$$” ($$$1 \le l < r \le n$$$)。

保证至少有一个第三类型的查询。

输出

对于第三种类型的每个查询,打印 $$$[l, r]$$$ 段内两个非空非重叠子数组的最大可能总成本。

示例

输入 #1

7
3 -1 4 -3 2 4 0
0 6 1 0 -3 -2 -1
6
3 1 7
1 2 0
3 3 6
2 5 -3
1 3 2
3 1 5

输出 #1

18
7
16

输入 #2

10
2 -1 -3 -2 0 4 5 6 2 5
2 -4 -5 -1 6 2 5 -6 4 2
10
3 6 7
1 10 -2
3 5 7
3 2 8
2 1 -5
2 7 4
3 1 3
3 3 8
3 2 3
1 4 4

输出 #2

23
28
28
-17
27
-22