← 返回题目列表

Codeforces · 1924/B

B. 太空港

中文机器翻译题面 查看原题

一条直线上有编号为 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 个点。最初,有 $$$m$$$ 港口。第 $$$i$$$ 个港口位于 $$$X_i$$$ 点,值为 $$$V_i$$$。保证 $$$1$$$ 和 $$$n$$$ 点有港口。每个 $$$n$$$ 点上恰好有一艘船。将船舶从当前位置移动到下一个港口的成本是其左侧最近港口的价值与其右侧最近港口距离的乘积。具体来说,如果一艘船已经停泊在一个港口,那么将其移至下一个港口的成本为$$$0$$$。

此外,还有 $$$q$$$ 查询,每个查询都是以下 $$$2$$$ 类型之一:

- $$$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$$$) — 第二种类型查询。

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

输出

对于每个第二类查询,在新行中打印一个整数 - 回答此查询。

示例

输入 #1

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

输出 #1

171
0
15

注意

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