/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
長さ N の整数列 A があります。
A の 空でない 連続する 部分列であって、その総和が 0 になるものの個数を求めてください。 ただし、ここで数えるのは 部分列の取り出し方 であることに注意してください。 つまり、ある 2 つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
A の空でない連続する部分列であって、その総和が 0 になるものの個数を出力せよ。
入力例 1
6 1 3 -4 2 2 -2
出力例 1
3
空でない連続した部分列であって、その総和が 0 になるのは、(1,3,-4), (-4,2,2), (2,-2) の 3 つです。
入力例 2
7 1 -1 1 -1 1 -1 1
出力例 2
12
この例では、列として同じだが取り出す位置の異なる部分列が複数回数えられています。 例えば、(1,-1) は 3 回数えられています。
入力例 3
5 1 -2 3 -4 5
出力例 3
0
空でない連続した部分列であって、その総和が 0 になるものはありません。
Score : 200 points
Problem Statement
We have an integer sequence A, whose length is N.
Find the number of the non-empty contiguous subsequences of A whose sums are 0. Note that we are counting the ways to take out subsequences. That is, even if the contents of some two subsequences are the same, they are counted individually if they are taken from different positions.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Find the number of the non-empty contiguous subsequences of A whose sum is 0.
Sample Input 1
6 1 3 -4 2 2 -2
Sample Output 1
3
There are three contiguous subsequences whose sums are 0: (1,3,-4), (-4,2,2) and (2,-2).
Sample Input 2
7 1 -1 1 -1 1 -1 1
Sample Output 2
12
In this case, some subsequences that have the same contents but are taken from different positions are counted individually. For example, three occurrences of (1, -1) are counted.
Sample Input 3
5 1 -2 3 -4 5
Sample Output 3
0
There are no contiguous subsequences whose sums are 0.