CF1924B Space Harbour

在一条直线上有 $n$ 个点，编号为 $1$ 到 $n$。初始时有 $m$ 个港口，第 $i$ 个港口位于点 $X_i$，其价值为 $V_i$。保证在点 $1$ 和点 $n$ 上都存在港口。每个点上恰好有一艘船。将一艘船从当前位置移动到下一个港口的代价为其左侧最近港口的价值与其右侧最近港口的距离的乘积。特别地，如果船已经在港口上，则将其移动到下一个港口的代价为 $0$。 此外，有 $q$ 个操作，每个操作为以下两种类型之一： - $1\ x\ v$ —— 在位置 $x$ 新建一个价值为 $v$ 的港口。保证在添加前，$x$ 处没有港口。 - $2\ l\ r$ —— 输出将 $l$ 到 $r$ 位置上的所有船移动到它们的下一个港口的总代价。注意只需计算代价，无需实际移动船只。

第一行包含三个整数 $n$、$m$ 和 $q$（$2 \le m \le n \le 3 \cdot 10^5$，$1 \le q \le 3 \cdot 10^5$）——点的数量、港口的数量和操作的数量。 第二行包含 $m$ 个互不相同的整数 $X_1, X_2, \ldots, X_m$（$1 \le X_i \le n$）——第 $i$ 个港口的位置。 第三行包含 $m$ 个整数 $V_1, V_2, \ldots, V_m$（$1 \le V_i \le 10^7$）——第 $i$ 个港口的价值。 接下来的 $q$ 行，每行包含三个整数。第一个整数为 $t$（$1 \le t \le 2$）——操作类型。如果 $t=1$，则接下来两个整数为 $x$ 和 $v$（$2 \le x \le n-1$，$1 \le v \le 10^7$）——第一类操作。如果 $t=2$，则接下来两个整数为 $l$ 和 $r$（$1 \le l \le r \le n$）——第二类操作。 保证至少有一个第二类操作。

对于每个第二类操作，输出一个整数，表示该操作的答案，每行一个。

对于第一个类型为 $2$ 的操作，位置 $2$、$3$、$4$ 和 $5$ 上的船的代价分别为 $3(3 \times 1)$、$0$、$96(24 \times 4)$ 和 $72(24 \times 3)$。 对于第二个类型为 $2$ 的操作，由于位置 $5$ 上的船已经在港口上，所以代价为 $0$。 对于第三个类型为 $2$ 的操作，位置 $7$ 和 $8$ 上的船的代价分别为 $15(15 \times 1)$ 和 $0$。 由 ChatGPT 4.1 翻译