← 返回题目列表

Codeforces · 1630/D

D. 翻转范围

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$ 和由 $$$m$$$ 正整数组成的 $$$B$$$ 集合,使得 $$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$ 对于 $$$1\le i\le m$$$,其中 $$$b_i$$$ 是$$$B$$$ 的 $$$i$$$ 个元素。

您可以对$$$a$$$进行以下操作:

1. 选择一些$$$x$$$,使$$$x$$$ 出现在$$$B$$$ 中。
2. 从大小为 $$$x$$$ 的数组 $$$a$$$ 中选择一个区间,并将区间中的每个元素乘以 $$$-1$$$。形式上,选择 $$$l$$$ 和 $$$r$$$,使得 $$$1\leq l\leq r \leq n$$$ 和 $$$r-l+1=x$$$,然后为每个 $$$i$$$ 分配 $$$a_i:=-a_i$$$,使得 $$$l\leq i\leq r$$$。

考虑以下示例,令 $$$a=[0,6,-2,1,-4,5]$$$ 和 $$$B=\{1,2\}$$$:

1. $$$[0,6,-2,-1,4,5]$$$是在选择尺寸$$$2$$$和$$$l=4$$$、$$$r=5$$$后得到的。
2. $$$[0,6,2,-1,4,5]$$$是选择尺寸$$$1$$$和$$$l=3$$$、$$$r=3$$$后得到的。

找到在应用此类操作任意次(可能为零)后可以获得的最大$$$\sum\limits_{i=1}^n {a_i}$$$。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\leq n \leq 10^6$$$, $$$1 \leq m \leq \lfloor \frac{n}{2} \rfloor$$$) — 分别是 $$$a$$$ 和 $$$B$$$ 的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\leq a_i \leq 10^9$$$)。

每个测试用例的第三行包含 $$$m$$$ 不同的正整数 $$$b_1,b_2,\ldots,b_m$$$ ($$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$) — 集合 $$$B$$$ 中的元素。

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

输出

对于每个测试用例,打印一个整数 - 应用此类操作任意次后所有 $$$a_i$$$ 的最大可能总和。

示例

输入 #1

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

输出 #1

18
5
5000000000

注意

在第一个测试中,您可以应用操作$$$x=1$$$、$$$l=3$$$、$$$r=3$$$,以及操作$$$x=1$$$、$$$l=5$$$、$$$r=5$$$,则数组变为$$$[0, 6, 2, 1, 4, 5]$$$。

在第二个测试中,可以应用操作 $$$x=2$$$, $$$l=2$$$, $$$r=3$$$,数组变为 $$$[1, 1, -1, -1, 1, -1, 1]$$$,然后应用操作 $$$x=2$$$, $$$l=3$$$, $$$r=4$$$,并且数组变为 $$$[1, 1, 1, 1, 1, -1, 1]$$$。没有办法获得超过 $$$5$$$ 的总和。