311041: CF1925E. Space Harbour

E. Space Harbourtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExampleInput

8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8

Output

171
0
15

Note

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.

题目大意：
在一条直线上有 n 个点，编号为 1 到 n。一开始有 m 个港口，第 i 个港口位于点 X_i，并且有一个值 V_i。保证点 1 和点 n 上有港口。每个点上恰好有一艘船。将船从当前位置移动到下一个港口的成本是左侧最近港口的值与右侧最近港口的距离的乘积。具体来说，如果船已经在港口，那么将其移动到下一个港口的成本是 0。

此外，还有 q 个查询，每个查询都是以下两种类型之一：
1. 1 x v — 在点 x 处添加一个值为 v 的港口。保证在添加港口之前，点 x 上没有港口。
2. 2 l r — 打印将点 l 到点 r 上的所有船移动到它们下一个港口的总成本。注意，只需计算移动船的成本，实际上不需要移动它们。

输入数据格式：
第一行包含三个整数 n、m 和 q（2 ≤ m ≤ n ≤ 3 × 10^5，1 ≤ q ≤ 3 × 10^5）——点的数量、港口的数量和查询的数量。
第二行包含 m 个不同的整数 X_1, X_2, …, X_m（1 ≤ X_i ≤ n）——第 i 个港口的位置。
第三行包含 m 个整数 V_1, V_2, …, V_m（1 ≤ V_i ≤ 10^7）——第 i 个港口的值。
接下来的 q 行每行包含三个整数。第一个整数是 t（1 ≤ t ≤ 2）——查询类型。如果 t=1，那么接下来的两个整数是 x 和 v（2 ≤ x ≤ n - 1，1 ≤ v ≤ 10^7）——第一种类型的查询。如果 t=2，那么接下来的两个整数是 l 和 r（1 ≤ l ≤ r ≤ n）——第二种类型的查询。
保证至少有一个第二种类型的查询。

输出数据格式：
对于每个第二种类型的查询，打印一行，包含一个整数——对该查询的答案。

示例：
输入：
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8
输出：
171
0
15

注意：
对于第一个第二种类型的查询，位置 2、3、4 和 5 的船的成本分别是 3(3 × 1)、0、96(24 × 4) 和 72(24 × 3)。
对于第二个第二种类型的查询，由于位置 5 的船已经在港口，所以成本是 0。
对于第三个第二种类型的查询，位置 7 和 8 的船的成本分别是 15(15 × 1) 和 0。题目大意： 在一条直线上有 n 个点，编号为 1 到 n。一开始有 m 个港口，第 i 个港口位于点 X_i，并且有一个值 V_i。保证点 1 和点 n 上有港口。每个点上恰好有一艘船。将船从当前位置移动到下一个港口的成本是左侧最近港口的值与右侧最近港口的距离的乘积。具体来说，如果船已经在港口，那么将其移动到下一个港口的成本是 0。 此外，还有 q 个查询，每个查询都是以下两种类型之一： 1. 1 x v — 在点 x 处添加一个值为 v 的港口。保证在添加港口之前，点 x 上没有港口。 2. 2 l r — 打印将点 l 到点 r 上的所有船移动到它们下一个港口的总成本。注意，只需计算移动船的成本，实际上不需要移动它们。 输入数据格式： 第一行包含三个整数 n、m 和 q（2 ≤ m ≤ n ≤ 3 × 10^5，1 ≤ q ≤ 3 × 10^5）——点的数量、港口的数量和查询的数量。 第二行包含 m 个不同的整数 X_1, X_2, …, X_m（1 ≤ X_i ≤ n）——第 i 个港口的位置。 第三行包含 m 个整数 V_1, V_2, …, V_m（1 ≤ V_i ≤ 10^7）——第 i 个港口的值。 接下来的 q 行每行包含三个整数。第一个整数是 t（1 ≤ t ≤ 2）——查询类型。如果 t=1，那么接下来的两个整数是 x 和 v（2 ≤ x ≤ n - 1，1 ≤ v ≤ 10^7）——第一种类型的查询。如果 t=2，那么接下来的两个整数是 l 和 r（1 ≤ l ≤ r ≤ n）——第二种类型的查询。 保证至少有一个第二种类型的查询。 输出数据格式： 对于每个第二种类型的查询，打印一行，包含一个整数——对该查询的答案。 示例： 输入： 8 3 4 1 3 8 3 24 10 2 2 5 1 5 15 2 5 5 2 7 8 输出： 171 0 15 注意： 对于第一个第二种类型的查询，位置 2、3、4 和 5 的船的成本分别是 3(3 × 1)、0、96(24 × 4) 和 72(24 × 3)。 对于第二个第二种类型的查询，由于位置 5 的船已经在港口，所以成本是 0。 对于第三个第二种类型的查询，位置 7 和 8 的船的成本分别是 15(15 × 1) 和 0。