1990C.md (2183B)
1 Source: https://codeforces.com/problemset/problem/1990/C 2 3 C. Mad MAD Sum 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 We define the $\operatorname{MAD}$ (Maximum Appearing Duplicate) in an array as the largest number that appears at least twice in the array. Specifically, if there is no number that appears at least twice, the $\operatorname{MAD}$ value is $0$. 22 23 For example, $\operatorname{MAD}([1, 2, 1]) = 1$, $\operatorname{MAD}([2, 2, 3, 3]) = 3$, $\operatorname{MAD}([1, 2, 3, 4]) = 0$. 24 25 You are given an array $a$ of size $n$. Initially, a variable $sum$ is set to $0$. 26 27 The following process will be executed in a sequential loop until all numbers in $a$ become $0$: 28 29 1. Set $sum := sum + \sum_{i=1}^{n} a_i$; 30 2. Let $b$ be an array of size $n$. Set $b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])$ for all $1 \le i \le n$, and then set $a_i := b_i$ for all $1 \le i \le n$. 31 32 Find the value of $sum$ after the process. 33 34 Input 35 36 The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. 37 38 For each test case: 39 40 * The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array $a$; 41 * The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array. 42 43 It is guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, output the value of $sum$ in a new line. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 1 57 58 1 59 60 3 61 62 2 2 3 63 64 4 65 66 2 1 1 2 67 68 4 69 70 4 4 4 4 71 ``` 72 73 Output 74 75 ``` 76 1 77 13 78 9 79 40 80 ``` 81 82 Note 83 84 In the first test case, $a=[1]$ initially. 85 86 In the first loop: 87 88 1. Set $sum := sum + a_1 = 0+1=1$; 89 2. Set $b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0$, and then set $a_1 := b_1$. 90 91 After the first loop, $a=[0]$ and the process ends. The value of $sum$ after the process is $1$. 92 93 In the second test case, $a=[2,2,3]$ initially. 94 95 After the first loop, $a=[0,2,2]$ and $sum=7$. 96 97 After the second loop, $a=[0,0,2]$ and $sum=11$. 98 99 After the third loop, $a=[0,0,0]$ and $sum=13$. Then the process ends. 100 101 The value of $sum$ after the process is $13$.