2248C.md (2419B)
1 Source: https://codeforces.com/problemset/problem/2248/C 2 3 C. Maximize the Score 4 5 time limit per test 6 7 2 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 You are given an array $a$ of length $2n$. Each integer from $1$ to $n$ occurs exactly twice in $a$. 22 23 Initially, your score is $0$. 24 25 You can repeatedly perform the following operation while $a$ is non-empty: 26 27 * Choose an integer $x$ that is present in $a$. 28 * Let $l$ and $r$ be the indices of the leftmost and rightmost occurrences of $x$ in the current array, respectively. If $x$ occurs only once, then $l = r$. 29 * Add $(r - l + 1)^2$ to your score. 30 * Delete the elements $a_l, a_{l + 1}, \ldots, a_r$ from $a$. The remaining elements are concatenated without changing their order and re-indexed starting from $1$. 31 32 Find the maximum possible score after making the array empty. 33 34 Input 35 36 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. 37 38 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$). 39 40 The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \le a_i \le n$). 41 42 It is guaranteed that each integer from $1$ to $n$ occurs exactly twice in $a$. 43 44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 45 46 Output 47 48 For each test case, output a single integer — the maximum possible score. 49 50 Example 51 52 Input 53 54 ``` 55 6 56 57 1 58 59 1 1 60 61 2 62 63 1 2 1 2 64 65 2 66 67 1 2 2 1 68 69 3 70 71 1 1 2 3 3 2 72 73 3 74 75 1 2 3 3 2 1 76 77 4 78 79 1 2 3 4 1 2 3 4 80 ``` 81 82 Output 83 84 ``` 85 4 86 87 10 88 89 16 90 91 20 92 93 36 94 95 28 96 ``` 97 98 Note 99 100 In the second test case, one optimal strategy is to choose $x = 1$ first. This deletes the subarray $[1, 2, 1]$ and adds $3^2 = 9$ to the score. The remaining array is $[2]$; choosing $x = 2$ adds $1$. The total score is $10$. 101 102 In the third test case, choosing $x = 1$ deletes the whole array and adds $4^2 = 16$ to the score. 103 104 In the fourth test case, choose $x = 1$ first and then choose $x = 2$. The total score is $2^2 + 4^2 = 20$. 105 106 In the sixth test case, choose $x = 2$ first. This deletes the subarray $[2, 3, 4, 1, 2]$ from the middle of the array and adds $5^2 = 25$ to the score. After deleting this subarray and concatenating the remaining elements, the array becomes $[1, 3, 4]$. Choosing each of the three remaining values then adds $1$, so the total score is $28$.