2222B.md (3524B)
1 Source: https://codeforces.com/problemset/problem/2222/B 2 3 B. Artistic Balance Tree 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 After learning about the Artistic Balance Tree, Lizhous encountered the following problem. 22 23 You are given an array $a$ consisting of $n$ integers. You need to perform exactly $m$ operations on $a$ in order. Each operation consists of two steps. Specifically, in the $i$-th operation, you are given an integer $x_i$, and you will: 24 25 * First, select a center index $u$ and a non-negative length $y$ such that the interval $[u-y, u+y]$ lies entirely within $[1, n]$ (i.e., $u - y \ge 1$ and $u + y \le n$). For each $1\le i\le y$, swap the elements $a_{u-i}$ and $a_{u+i}$. 26 * Then, mark the element at index $x_i$. If this element is already marked, nothing happens. Note that the marks are on elements, not indices. That means if an element is swapped with some other element by future operations, the mark will stay on it. 27 28 After performing all $m$ operations, your task is to find the minimum possible sum of all elements that remain unmarked. 29 30 Input 31 32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 33 34 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the length of $a$ and the number of operations. 35 36 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of $a$. 37 38 The third line contains $m$ integers $x_1, x_2, \ldots, x_m$ ($1 \le x_i \le n$) — the indices to be marked in each operation. 39 40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 41 42 It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$. 43 44 Output 45 46 For each test case, output a single integer — the minimum possible sum of the unmarked elements after all operations. 47 48 Example 49 50 Input 51 52 ``` 53 6 54 55 7 4 56 57 1 2 3 4 5 6 7 58 59 1 2 3 4 60 61 7 4 62 63 1 -2 3 4 -5 -6 -7 64 65 7 6 5 4 66 67 7 5 68 69 21 -45 234 -8 423 12 -987 70 71 6 6 6 6 6 72 73 7 5 74 75 -21 45 -234 8 -423 -12 987 76 77 7 7 7 7 7 78 79 7 3 80 81 -1 2 -3 4 5 6 7 82 83 1 2 3 84 85 7 3 86 87 -1 -2 -3 -4 -5 -6 -7 88 89 1 2 3 90 ``` 91 92 Output 93 94 ``` 95 6 96 97 -20 98 99 -362 100 101 -637 102 103 2 104 105 -25 106 ``` 107 108 Note 109 110 In the first test case, one optimal operation sequence is as follows: 111 112 1. Choose center $u=4$ and length $y=3$, and $a$ becomes $[7,6,5,4,3,2,1]$. Then, the element $a_1=7$ is marked. 113 2. Choose center $u=1$ and length $y=0$, and $a$ remains $[7,6,5,4,3,2,1]$. Then, the element $a_2=6$ is marked. 114 3. Choose center $u=1$ and length $y=0$, and $a$ remains $[7,6,5,4,3,2,1]$. Then, the element $a_3=5$ is marked. 115 4. Choose center $u=1$ and length $y=0$, and $a$ remains $[7,6,5,4,3,2,1]$. Then, the element $a_4=4$ is marked. 116 117 The unmarked elements are $1$, $2$, and $3$, and the answer is $1+2+3=6$. 118 119 In the second test case, one optimal operation sequence is as follows: 120 121 1. Choose center $u=4$ and length $y=3$, and $a$ becomes $[-7,-6,-5,4,3,-2,1]$. Then, the element $a_7=1$ is marked. 122 2. Choose center $u=5$ and length $y=1$, and $a$ becomes $[-7,-6,-5,-2,3,4,1]$. Then, the element $a_6=4$ is marked. 123 3. Choose center $u=1$ and length $y=0$, and $a$ remains $[-7,-6,-5,-2,3,4,1]$. Then, the element $a_5=3$ is marked. 124 4. Choose center $u=5$ and length $y=1$, and $a$ becomes $[-7,-6,-5,4,3,-2,1]$. Then, the element $a_4=4$ is marked. 125 126 The unmarked elements are $-2$, $-5$, $-6$, and $-7$, and the answer is $(-2)+(-5)+(-6)+(-7)=-20$.