Flipping Range

题意翻译

给定一个长度为 $n$ 的数组 $a$ 和一个包含 $m$ 个正整数的集合 $b$，保证对于所有的 $1\leqslant i\leqslant m$，都有 $1\leqslant b_i\leqslant \lfloor\frac n2\rfloor$。你可以对 $a$ 数组执行若干次操作，每次操作中，你可以： - 选出一个在 $b$ 集合中出现过的数 $x$。 - 选择 $a$ 数组中一个长度为 $x$ 的子段，然后将该子段里的所有元素的值变为其相反数。形式化地来说，选出满足 $1\leqslant l\leqslant r\leqslant n$ 且 $r-l+1=x$ 的两个数 $l,r$，然后对于所有的 $l\leqslant i\leqslant r$，将 $a_i$ 替换为 $-a_i$。 你希望最大化 $\sum\limits_{i=1}^n a_i$ 的值，求这个最大值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^5$。 - $2\leqslant n,\sum n\leqslant 10^6$，$1\leqslant m\leqslant\lfloor\frac n2\rfloor$。 - $-10^9\leqslant a_i\leqslant 10^9$，$1\leqslant b_i\leqslant\lfloor\frac n2\rfloor$。 Translated by Eason_AC 2022.1.28

题目描述

You are given an array $ a $ of $ n $ integers and a set $ B $ of $ m $ positive integers such that $ 1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor $ for $ 1\le i\le m $ , where $ b_i $ is the $ i $ -th element of $ B $ . You can make the following operation on $ a $ : 1. Select some $ x $ such that $ x $ appears in $ B $ . 2. Select an interval from array $ a $ of size $ x $ and multiply by $ -1 $ every element in the interval. Formally, select $ l $ and $ r $ such that $ 1\leq l\leq r \leq n $ and $ r-l+1=x $ , then assign $ a_i:=-a_i $ for every $ i $ such that $ l\leq i\leq r $ . Consider the following example, let $ a=[0,6,-2,1,-4,5] $ and $ B=\{1,2\} $ : 1. $ [0,6,-2,-1,4,5] $ is obtained after choosing size $ 2 $ and $ l=4 $ , $ r=5 $ . 2. $ [0,6,2,-1,4,5] $ is obtained after choosing size $ 1 $ and $ l=3 $ , $ r=3 $ . Find the maximum $ \sum\limits_{i=1}^n {a_i} $ you can get after applying such operation any number of times (possibly zero).

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2\leq n \leq 10^6 $ , $ 1 \leq m \leq \lfloor \frac{n}{2} \rfloor $ ) — the number of elements of $ a $ and $ B $ respectively. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -10^9\leq a_i \leq 10^9 $ ). The third line of each test case contains $ m $ distinct positive integers $ b_1,b_2,\ldots,b_m $ ( $ 1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor $ ) — the elements in the set $ B $ . It's guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case print a single integer — the maximum possible sum of all $ a_i $ after applying such operation any number of times.

输入输出样例

输入样例 #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

说明

In the first test, you can apply the operation $ x=1 $ , $ l=3 $ , $ r=3 $ , and the operation $ x=1 $ , $ l=5 $ , $ r=5 $ , then the array becomes $ [0, 6, 2, 1, 4, 5] $ . In the second test, you can apply the operation $ x=2 $ , $ l=2 $ , $ r=3 $ , and the array becomes $ [1, 1, -1, -1, 1, -1, 1] $ , then apply the operation $ x=2 $ , $ l=3 $ , $ r=4 $ , and the array becomes $ [1, 1, 1, 1, 1, -1, 1] $ . There is no way to achieve a sum bigger than $ 5 $ .

题意翻译

给定一个长度为 $n$ 的数组 $a$ 和一个包含 $m$ 个正整数的集合 $b$，保证对于所有的 $1\leqslant i\leqslant m$，都有 $1\leqslant b_i\leqslant \lfloor\frac n2\rfloor$。你可以对 $a$ 数组执行若干次操作，每次操作中，你可以： - 选出一个在 $b$ 集合中出现过的数 $x$。 - 选择 $a$ 数组中一个长度为 $x$ 的子段，然后将该子段里的所有元素的值变为其相反数。形式化地来说，选出满足 $1\leqslant l\leqslant r\leqslant n$ 且 $r-l+1=x$ 的两个数 $l,r$，然后对于所有的 $l\leqslant i\leqslant r$，将 $a_i$ 替换为 $-a_i$。 你希望最大化 $\sum\limits_{i=1}^n a_i$ 的值，求这个最大值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^5$。 - $2\leqslant n,\sum n\leqslant 10^6$，$1\leqslant m\leqslant\lfloor\frac n2\rfloor$。 - $-10^9\leqslant a_i\leqslant 10^9$，$1\leqslant b_i\leqslant\lfloor\frac n2\rfloor$。 Translated by Eason_AC 2022.1.28