Romantic Glasses
Contest: Codeforces Round 918 (Div. 4)
Difficulty rating: 1300
Tags: data structures, greedy, math

Iulia has $$$n$$$ glasses arranged in a line. The $$$i$$$-th glass has $$$a_i$$$ units of juice in it. Iulia drinks only from odd-numbered glasses, while her date drinks only from even-numbered glasses.

To impress her date, Iulia wants to find a contiguous subarray of these glasses such that both Iulia and her date will have the same amount of juice in total if only the glasses in this subarray are considered. Please help her to do that.

More formally, find out if there exists two indices $$$l$$$, $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$, and $$$a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}$$$ if $$$l$$$ and $$$r$$$ have the same parity and $$$a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r - 1} = a_{l + 1} + a_{l + 3} + \dots + a_{r}$$$ otherwise.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the total number of glasses.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the amount of juice in each glass.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output "YES" if there exists a subarray satisfying the condition, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Iulia can pick $$$l=1$$$ and $$$r=3$$$. Then she drinks $$$a_1+a_3=1+2=3$$$ units and her date drinks $$$a_2=3$$$ units of juice.

In the second test case, Iulia can pick $$$l=2$$$ and $$$r=5$$$. Then she drinks $$$a_3+a_5=1+1=2$$$ units and her date drinks $$$a_2+a_4=1+1=2$$$ units of juice.

In the third test case no such contiguous subarray works.

In the fourth test case, Iulia can pick $$$l=2$$$ and $$$r=8$$$. Then she drinks $$$a_3+a_5+a_7=11+1+1=13$$$ units and her date drinks $$$a_2+a_4+a_6+a_8=2+4+5+2=13$$$ units of juice.

Example input:
6
3
1 3 2
6
1 1 1 1 1 1
10
1 6 9 8 55 3 14 2 7 2
8
1 2 11 4 1 5 1 2
6
2 6 1 5 7 8
9
2 5 10 4 4 9 6 7 8

Example output:
YES
YES
NO
YES
NO
YES

Editorial:
Let's rewrite the given equation: $$$a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}$$$ as $$$$$$a_l - a_{l+1} + a_{l + 2} - a_{l+3} + a_{l + 4} + \dots - a_{r-1} + a_{r} = 0.$$$$$$ From here, it's clear that we need to find if there is a subarray with alternating sum equal to $$$0$$$.
How to check this? Let's flip all elements on even indices $$$a_2 \to -a_2, a_4 \to -a_4, \dots$$$. Then alternating sums of $$$[a_1, a_2, a_3, a_4, \dots]$$$ are the same as subarray sums on $$$[a_1, -a_2, a_3, -a_4, \dots]$$$.
So we just need to check if there is a subarray with sum $$$0$$$. This is a standard problem with prefix sums: if two prefix sums are equal, then the subarray between them has sum $$$0$$$; otherwise, no subarray has sum $$$0$$$.
The complexity is $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \log n)$$$ depending on how you check if two elements of an array are equal. Be careful about using hash tables, as they can be hacked.