1748C.md (1888B)
1 Source: https://codeforces.com/problemset/problem/1748/C 2 3 C. Zero-Sum Prefixes 4 5 time limit per test 6 7 1 second 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 The score of an array $v_1,v_2,\ldots,v_n$ is defined as the number of indices $i$ ($1 \le i \le n$) such that $v_1+v_2+\ldots+v_i = 0$. 22 23 You are given an array $a_1,a_2,\ldots,a_n$ of length $n$. You can perform the following operation multiple times: 24 25 * select an index $i$ ($1 \le i \le n$) such that $a_i=0$; 26 * then replace $a_i$ by an arbitrary integer. 27 28 What is the maximum possible score of $a$ that can be obtained by performing a sequence of such operations? 29 30 Input 31 32 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$. 35 36 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9 \le a_i \le 10^9$) — array $a$. 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, print the maximum possible score of the array $a$ after performing a sequence of operations. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 5 52 53 2 0 1 -1 0 54 55 3 56 57 1000000000 1000000000 0 58 59 4 60 61 0 0 0 0 62 63 8 64 65 3 0 2 -10 10 -30 30 0 66 67 9 68 69 1 0 0 1 -1 0 1 0 -1 70 ``` 71 72 Output 73 74 ``` 75 3 76 1 77 4 78 4 79 5 80 ``` 81 82 Note 83 84 In the first test case, it is optimal to change the value of $a_2$ to $-2$ in one operation. 85 86 The resulting array $a$ will be $[2,-2,1,-1,0]$, with a score of $3$: 87 88 * $a_1+a_2=2-2=0$; 89 * $a_1+a_2+a_3+a_4=2-2+1-1=0$; 90 * $a_1+a_2+a_3+a_4+a_5=2-2+1-1+0=0$. 91 92 In the second test case, it is optimal to change the value of $a_3$ to $-2\,000\,000\,000$, giving us an array with a score of $1$. 93 94 In the third test case, it is not necessary to perform any operations.