A Stroll Around the Matrix

题意翻译

给定两个长度为 $n,m$ 的正整数严格上升序列 $a,b$，并且这两个序列的差分数组也是严格上升的。 $q$ 次操作，每次操作对 $a,b$ 中的一个序列 $x$ 的最后 $k$ 个位置加首项与公差均为 $d$，长度为 $k$ 的等差数列，也就是 $\forall i\in[n-k+1,n],x_i\leftarrow x_i+d(i-n+k)$。 每次操作后，用 $a,b$ 构造一个大小为 $n\times m$ 的矩阵 $d$，$d_{i,j}=a_i+b_j$。询问从 $(1,1)$ 走到 $(n,m)$ 并且只能向下或向右，经过位置 $d_{i,j}$ 的和的最小值。 $2\le n\le 100,2\le m\le 10^5,1\le q\le 10^5,1\le a_i,b_i\le 10^{12},1\le d\le 10^3$。

题目描述

William has two arrays of numbers $ a_1, a_2, \dots, a_n $ and $ b_1, b_2, \dots, b_m $ . The arrays satisfy the conditions of being convex. Formally an array $ c $ of length $ k $ is considered convex if $ c_i - c_{i - 1} < c_{i + 1} - c_i $ for all $ i $ from $ 2 $ to $ k - 1 $ and $ c_1 < c_2 $ . Throughout William's life he observed $ q $ changes of two types happening to the arrays: 1. Add the arithmetic progression $ d, d \cdot 2, d \cdot 3, \dots, d \cdot k $ to the suffix of the array $ a $ of length $ k $ . The array after the change looks like this: $ [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. The same operation, but for array $ b $ . After each change a matrix $ d $ is created from arrays $ a $ and $ b $ , of size $ n \times m $ , where $ d_{i, j}=a_i + b_j $ . William wants to get from cell ( $ 1, 1 $ ) to cell ( $ n, m $ ) of this matrix. From cell ( $ x, y $ ) he can only move to cells ( $ x + 1, y $ ) and ( $ x, y + 1 $ ). The length of a path is calculated as the sum of numbers in cells visited by William, including the first and the last cells. After each change William wants you to help find out the minimal length of the path he could take.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ q $ ( $ 2 \le n \le 100, 2 \le m \le 10^5 $ , $ 1 \le q \le 10^5 $ ), the sizes of the arrays and the number of changes. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ), the contents of array $ a $ . The third line contains $ m $ integers $ b_1, b_2, \dots, b_m $ ( $ 1 \le b_i \le 10^{12} $ ), the contents of array $ b $ . Each of the next $ q $ lines contains three integers $ type $ , $ k $ and $ d $ ( $ 1 \le type \le 2 $ , if $ type = 1 $ , then $ 1 \le k \le n $ otherwise $ 1 \le k \le m $ , $ 1 \le d \le 10^3 $ ).

输出格式

After each change, output one integer, the minimum length of the path in the constructed matrix.

输入输出样例

输入样例 #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