← 返回题目列表

Codeforces · 2222/B

B. 艺术平衡树

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

学习了艺术平衡树后,利洲人遇到了以下问题。

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您需要按顺序对 $$$a$$$ 执行精确的 $$$m$$$ 操作。每个操作由两个步骤组成。具体来说,在第 $$$i$$$ 操作中,您将获得一个整数 $$$x_i$$$,您将:

  • 首先,选择中心索引 $$$u$$$ 和非负长度 $$$y$$$,使得区间 $$$[u-y, u+y]$$$ 完全位于 $$$[1, n]$$$ 内(即 $$$u - y \ge 1$$$ 和 $$$u + y \le n$$$)。对于每个 $$$1\le i\le y$$$,交换元素 $$$a_{u-i}$$$ 和 $$$a_{u+i}$$$。
  • 然后, 标记 这 元素 位于索引 $$$x_i$$$。如果该元素已被标记,则不会发生任何事情。请注意,标记位于元素上,而不是索引上。这意味着如果将来的操作将某个元素与其他元素交换,该标记将保留在其上。

执行完所有 $$$m$$$ 操作后,您的任务是找到剩余所有元素的最小可能总和 未标记.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — $$$a$$$ 的长度和操作数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — $$$a$$$ 的元素。

第三行包含 $$$m$$$ 整数 $$$x_1, x_2, \ldots, x_m$$$ ($$$1 \le x_i \le n$$$) — 索引 已标记 在每个操作中。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 的最小可能总和 所有操作后的 未标记 元素。

示例

输入
复制

6
7 4
1 2 3 4 5 6 7
1 2 3 4
7 4
1 -2 3 4 -5 -6 -7
7 6 5 4
7 5
21 -45 234 -8 423 12 -987
6 6 6 6 6
7 5
-21 45 -234 8 -423 -12 987
7 7 7 7 7
7 3
-1 2 -3 4 5 6 7
1 2 3
7 3
-1 -2 -3 -4 -5 -6 -7
1 2 3

输出
复制

6
-20
-362
-637
2
-25

注意

在第一个测试用例中,一个最佳操作顺序如下:

  1. 选择中心 $$$u=4$$$ 和长度 $$$y=3$$$,$$$a$$$ 变为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_1=7$$$ 为 已标记.
  2. 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 仍为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_2=6$$$ 为 已标记.
  3. 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 仍为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_3=5$$$ 为 已标记.
  4. 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 仍为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_4=4$$$ 为 已标记.

未标记的元素是$$$1$$$、$$$2$$$和$$$3$$$,答案是$$$1+2+3=6$$$。

在第二个测试用例中,一个最佳操作顺序如下:

  1. 选择中心 $$$u=4$$$ 和长度 $$$y=3$$$,$$$a$$$ 变为 $$$[-7,-6,-5,4,3,-2,1]$$$。那么,元素 $$$a_7=1$$$ 为 已标记.
  2. 选择中心 $$$u=5$$$ 和长度 $$$y=1$$$,$$$a$$$ 变为 $$$[-7,-6,-5,-2,3,4,1]$$$。那么,元素 $$$a_6=4$$$ 为 已标记.
  3. 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 保持 $$$[-7,-6,-5,-2,3,4,1]$$$。那么,元素 $$$a_5=3$$$ 为 已标记.
  4. 选择中心 $$$u=5$$$ 和长度 $$$y=1$$$,$$$a$$$ 变为 $$$[-7,-6,-5,4,3,-2,1]$$$。那么,元素 $$$a_4=4$$$ 为 已标记.

未标记的元素为 $$$-2$$$、$$$-5$$$、$$$-6$$$ 和 $$$-7$$$,答案为 $$$(-2)+(-5)+(-6)+(-7)=-20$$$。