CF1924B.Space Harbour

There are $n$ points numbered $1$ to $n$ on a straight line. Initially, there are $m$ harbours. The $i$-th harbour is at point $X_i$ and has a value $V_i$. It is guaranteed that there are harbours at the points $1$ and $n$. There is exactly one ship on each of the $n$ points. The cost of moving a ship from its current location to the next harbour is the product of the value of the nearest harbour to its left and the distance from the nearest harbour to its right. Specifically, if a ship is already at a harbour, the cost of moving it to the next harbour is $0$.

Additionally, there are $q$ queries, each of which is either of the following $2$ types:

• $1$ $x$ $v$ — Add a harbour at point $x$ with value $v$. It is guaranteed that before adding the harbour, there is no harbour at point $x$.
• $2$ $l$ $r$ — Print the sum of the cost of moving all ships at points from $l$ to $r$ to their next harbours. Note that you just need to calculate the cost of moving the ships but not actually move them.

一条直线上有编号为 $1$ 到 $n$ 的 $n$ 个点。初始时有 $m$ 个港口。第 $i$ 个港口位于点 $X_i$，其值为 $V_i$。保证点 $1$ 和点 $n$ 处均设有港口。每个点上恰好停泊一艘船。

将一艘船从其当前位置移动到下一个港口的代价，定义为：其左侧最近港口的值 与 其右侧最近港口的距离 的乘积。特别地，若一艘船当前已位于某个港口，则将其移动到下一个港口的代价为 $0$。

此外，还有 $q$ 个查询，每个查询属于以下两种类型之一：

• 1 x v — 在点 $x$ 新增一个值为 $v$ 的港口。保证在添加前点 $x$ 上没有港口。
• 2 l r — 输出所有位于区间 $[l, r]$ 内各点上的船，分别移动到各自下一个港口所需代价的总和。注意：你只需计算移动代价，而无需实际移动船只。

The first line contains three integers $n$, $m$, and $q$ ($2 \le m \le n \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$) — the number of points, harbours, and queries, respectively.

The second line contains $m$ distinct integers $X_1, X_2, \ldots, X_m(1 \le X_i \le n)$ — the position at which the $i$-th harbour is located.

The third line contains $m$ integers $V_1, V_2, \ldots, V_m(1 \le V_i \le 10^7)$ — the value of the $i$-th harbour.

Each of the next $q$ lines contains three integers. The first integer is $t$ ($1\le t \le 2$) — type of query. If $t=1$, then the next two integers are $x$ and $v$ ($2 \le x \le n - 1$, $1 \le v \le 10^7$) — first-type query. If $t=2$, then the next two integers are $l$ and $r$ ($1 \le l \le r \le n$) — second-type query.

It is guaranteed that there is at least one second-type query.

第一行包含三个整数 $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$），表示第二类查询。

保证至少存在一个第二类查询。

For every second-type query, print one integer in a new line — answer to this query.

对于每个第二类查询，在新的一行中输出一个整数——该查询的答案。

For the first type $2$ query, the cost for ships at positions $2$, $3$, $4$ and $5$ are $3(3 \times 1)$, $0$, $96(24 \times 4)$ and $72(24 \times 3)$ respectively.

For the second type $2$ query, since the ship at position $5$ is already at a harbour, so the cost is $0$.

For the third type $2$ query, the cost for ships at position $7$ and $8$ are $15(15 \times 1)$ and $0$ respectively.

对于第一个类型 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$。