CF2222B Artistic Balance Tree

在学习了艺术平衡树之后，Lizhous 遇到了如下问题。 给定一个由 $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$。

对于每个测试用例，输出一个整数，即所有未被标记元素的最小可能和。

在第一个测试用例中，一种最优的操作顺序如下： 1. 选择中心 $u=4$，长度 $y=3$，$a$ 变为 $[7,6,5,4,3,2,1]$。然后标记下标 $1$ 的元素 $a_1=7$。 2. 选择中心 $u=1$，长度 $y=0$，$a$ 保持为 $[7,6,5,4,3,2,1]$。然后标记下标 $2$ 的元素 $a_2=6$。 3. 选择中心 $u=1$，长度 $y=0$，$a$ 保持为 $[7,6,5,4,3,2,1]$。然后标记下标 $3$ 的元素 $a_3=5$。 4. 选择中心 $u=1$，长度 $y=0$，$a$ 保持为 $[7,6,5,4,3,2,1]$。然后标记下标 $4$ 的元素 $a_4=4$。 未被标记的元素为 $1$、$2$ 和 $3$，答案为 $1+2+3=6$。 在第二个测试用例中，一种最优的操作顺序如下： 1. 选择中心 $u=4$，长度 $y=3$，$a$ 变为 $[-7,-6,-5,4,3,-2,1]$。然后标记下标 $7$ 的元素 $a_7=1$。 2. 选择中心 $u=5$，长度 $y=1$，$a$ 变为 $[-7,-6,-5,-2,3,4,1]$。然后标记下标 $6$ 的元素 $a_6=4$。 3. 选择中心 $u=1$，长度 $y=0$，$a$ 保持为 $[-7,-6,-5,-2,3,4,1]$。然后标记下标 $5$ 的元素 $a_5=3$。 4. 选择中心 $u=5$，长度 $y=1$，$a$ 变为 $[-7,-6,-5,4,3,-2,1]$。然后标记下标 $4$ 的元素 $a_4=4$。 未被标记的元素为 $-2$、$-5$、$-6$、$-7$，答案为 $(-2)+(-5)+(-6)+(-7)=-20$。 由 ChatGPT 5 翻译