← 返回题目列表

Codeforces · 1609/G

G. 在矩阵中漫步

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

William 有两个数字数组 $$$a_1, a_2, \dots, a_n$$$ 和 $$$b_1, b_2, \dots, b_m$$$。数组满足凸条件。形式上,如果 $$$c_i - c_{i - 1} < c_{i + 1} - c_i$$$ 对于从 $$$2$$$ 到 $$$k - 1$$$ 的所有 $$$i$$$ 且 $$$c_1 < c_2$$$,则长度为 $$$k$$$ 的数组 $$$c$$$ 被视为凸数组。

在 William 的一生中,他观察到数组发生了两种类型的 $$$q$$$ 变化:

1. 将等差数列 $$$d, d \cdot 2, d \cdot 3, \dots, d \cdot k$$$ 添加到长度为 $$$k$$$ 的数组 $$$a$$$ 的后缀。更改后的数组如下所示:$$$[a_1, a_2, \dots, a_{n - k}, a_{n - k + 1} + d, a_{n - k + 2} + d \cdot 2, \dots, a_n + d \cdot k]$$$。
2. 相同的操作,但针对数组$$$b$$$。

每次更改后,都会从数组 $$$a$$$ 和 $$$b$$$ 创建一个矩阵 $$$d$$$,大小为 $$$n \times m$$$,其中 $$$d_{i, j}=a_i + b_j$$$。 William 想要从该矩阵的单元格 ($$$1, 1$$$) 到单元格 ($$$n, m$$$)。从单元格 ($$$x, y$$$) 他只能移动到单元格 ($$$x + 1, y$$$) 和 ($$$x, y + 1$$$)。路径的长度计算为 William 访问过的单元格中的数字之和,包括第一个和最后一个单元格。

在每次改变之后,威廉希望你帮助找出他可以采取的最小路径长度。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2 \le n \le 100、2 \le m \le 10^5$$$、$$$1 \le q \le 10^5$$$)、数组的大小和更改的数量。

第二行包含$$$n$$$整数$$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$),数组$$$a$$$的内容。

第三行包含$$$m$$$整数$$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^{12}$$$),数组$$$b$$$的内容。

接下来的 $$$q$$$ 行包含三个整数 $$$type$$$、$$$k$$$ 和 $$$d$$$ ($$$1 \le type \le 2$$$, 如果 $$$type = 1$$$, 则 $$$1 \le k \le n$$$ 否则 $$$1 \le k \le m$$$, $$$1 \le d \le 10^3$$$)。

输出

每次改变后,输出一个整数,即构造矩阵中路径的最小长度。

示例

输入 #1

5 3 4
1 2 4 7 11
5 7 10
1 3 2
2 2 5
1 5 4
2 1 7

输出 #1

98
128
219
229

输入 #2

5 6 7
4 9 22 118 226
7 94 238 395 565 738
2 1 95
1 4 54
1 2 5
1 2 87
2 6 62
2 1 143
1 1 77

输出 #2

3639
5122
5162
5617
7663
7806
7960