CF1609G A Stroll Around the Matrix

 William 有两个数列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_m$。这两个数列都满足凸性条件。形式化地说，长度为 $k$ 的数列 $c$ 被认为是凸的，当且仅当对于所有 $i$ 满足 $2 \le i \le k-1$，都有 $c_i - c_{i-1} < c_{i+1} - c_i$，且 $c_1 < c_2$。 在 William 的一生中，他观察到了 $q$ 次对这两个数列的变化，变化有两种类型： 1. 对数列 $a$ 的后缀长度为 $k$ 的部分，加上等差数列 $d, d \cdot 2, d \cdot 3, \dots, d \cdot k$。变化后的数列为 $[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$。 每次变化后，William 会用 $a$ 和 $b$ 构造一个 $n \times m$ 的矩阵 $d$，其中 $d_{i,j} = a_i + b_j$。William 想从单元格 $(1,1)$ 走到单元格 $(n,m)$。他每次只能向下 $(x+1, y)$ 或向右 $(x, y+1)$ 移动。路径的长度定义为经过的所有单元格的数值之和，包括起点和终点。 每次变化后，William 希望你帮他计算在构造出的矩阵中，从 $(1,1)$ 到 $(n,m)$ 的最短路径长度。

第一行包含三个整数 $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$），表示一次变化。

每次变化后，输出一个整数，表示构造出的矩阵中最短路径的长度。

由 ChatGPT 4.1 翻译