Kousuke's Assignment
Contest: Codeforces Round 981 (Div. 3)
Difficulty rating: 1300
Tags: data structures, dp, dsu, greedy, math

After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment. In this assignment, the teacher gave him an array $$$a$$$ of $$$n$$$ integers and asked him to calculate the number of non-overlapping segments of the array $$$a$$$, such that each segment is considered beautiful.

A segment $$$[l,r]$$$ is considered beautiful if $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r=0$$$.

For a fixed array $$$a$$$, your task is to compute the maximum number of non-overlapping beautiful segments.

Input format:
The first line of input contains the number $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Each test case consists of $$$2$$$ lines.

- The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.
- The second line contains $$$n$$$ integers $$$a_i$$$ ($$$-10^5 \le a_i \le 10^5$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3\cdot 10^5$$$.

Output format:
For each test case, output a single integer: the maximum number of non-overlapping beautiful segments.

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

Example input:
3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1

Example output:
1
2
3

Editorial:
For this task we were supposed to find the biggest amount of non-intersecting segments all of which have their sum equal to zero.
First of all, the problem "find the maximal number of non-intersecting segments" is an exaxmple of a classic dynamic programming problem.
First of all, we will sort all our segments by their right end in an increasing order.
After that, we will be processing all segments one by one and updating our answer as follows:
For a segment with fixed ends $$$l,r$$$, we will be updating our answer as follows.
$$$$$$dp_r=max(dp_{r-1},dp_{l-1}+1)$$$$$$
Because we are processing all our segments one by one in that order, when we start computing $$$dp_r$$$, for all $$$i<r$$$ the maximal possible answer will already be computed.
By filling the $$$dp$$$ array in this way, we are sure that the answer will always be contained in $$$dp_n$$$.
Now back to our task:
First of all, if we construct an array $$$p$$$ where $$$p_i=\sum^i_{j=1}a_i$$$, $$$(p_0=0)$$$ then for every segment which has sum equal to $$$0$$$, $$$p_{l-1}=p_r$$$.
It can be easily proven that for fixed $$$r$$$ there is at most one segment which will be useful for the optimal answer:
If there is no $$$p_l$$$ where $$$l<r$$$ such that $$$p_l=p_r$$$, then there is no segment that ends in position $$$r$$$.
Otherwise, it is sufficient to choose the one with the largest $$$l$$$. That is because if we chose the one with $$$l_1<l$$$, then we would have missed segment $$$[l_1+1,l]$$$. Because of that miss, we would not have found the correct answer for our $$$r$$$.
So our final algorithm would be to find the smallest segments that end in position $$$r$$$ and have their sum equal to $$$0$$$.
After that we can compute the answer by simply solving the maximal number of non-intersecting segments problem using dynamic programming.
Total tme complexity $$$O(nlogn)$$$ or $$$O(n)$$$ depending on implementation.