← 返回题目列表

Codeforces · 1495/F

F. 正方形

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

地板上从左到右绘制了$$$n$$$ 个方块。第 $$$i$$$ 个方格上写有三个整数 $$$p_i,a_i,b_i$$$。序列 $$$p_1,p_2,\dots,p_n$$$ 形成一个排列。

每轮你将从最左边的方块 $$$1$$$ 开始跳到右边。如果您现在位于第 $$$i$$$ 格,您可以执行以下两个操作之一:

1.跳到第$$$i+1$$$个方格并支付费用$$$a_i$$$。如果$$$i=n$$$,那么你可以结束回合并支付费用$$$a_i$$$。
2.跳转到第$$$j$$$个方格并支付成本$$$b_i$$$,其中$$$j$$$是满足$$$j > i, p_j > p_i$$$的最左边的方格。如果没有这样的$$$j$$$,那么你可以结束回合并支付费用$$$b_i$$$。

游戏中有 $$$q$$$ 轮。为了让游戏变得更加困难,你需要维护一个正方形集合$$$S$$$(最初它是空的)。回合中你必须通过这些方格(其他方格也可以通过)。第$$$i$$$轮的方格集$$$S$$$是通过从第$$$(i-1)$$$轮的方格集中添加或删除一个方格来获得的。

对于每一轮,找出结束该轮所需支付的最低成本。

输入

第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1\le n,q\le 2 \cdot 10^5$$$) — 方格数和回合数。

第二行包含 $$$n$$$ 不同的整数 $$$p_1,p_2,\dots,p_n$$$ ($$$1\le p_i\le n$$$)。保证序列 $$$p_1,p_2,\dots,p_n$$$ 形成一个排列。

第三行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$)。

第四行包含 $$$n$$$ 整数 $$$b_1,b_2,\dots,b_n$$$ ($$$-10^9\le b_i\le 10^9$$$)。

然后是 $$$q$$$ 行,其中 $$$i$$$ 包含一个整数 $$$x_i$$$ ($$$1\le x_i\le n$$$)。如果 $$$x_i$$$ 位于第 $$$(i-1)$$$ 轮的集合 $$$S$$$ 中,则应将其删除,否则应添加它。

输出

打印 $$$q$$$ 行,每一行都应包含一个整数 - 结束相应回合所需支付的最低成本。

示例

输入 #1

3 2
2 1 3
10 -5 4
3 -2 3
1
2

输出 #1

6
8

输入 #2

5 4
2 1 5 3 4
6 -5 3 -10 -1
0 3 2 7 2
1
2
3
2

输出 #2

-8
-7
-7
-8

注意

让我们将角色 $$$T$$$ 视为一轮的结束。然后我们可以为第一个和第二个测试绘制两个图表。

在第一个测试的第一轮中,您必须通过的集合是$$$\{1\}$$$。您可以使用的路径是$$$1\to 3\to T$$$,其成本是$$$6$$$。

在第一个测试的第二轮中,您必须通过的集合是$$$\{1,2\}$$$。您可以使用的路径是$$$1\to 2\to 3\to T$$$,其成本是$$$8$$$。