【Codeforces 1426 D】Non-zero Segments，贪心，前缀和，数组子段统计

problem

D. Non-zero Segments
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Kolya got an integer array a1,a2,…,an. The array can contain both positive and negative integers, but Kolya doesn’t like 0, so the array doesn’t contain any zeros.

Kolya doesn’t like that the sum of some subsegments of his array can be 0. The subsegment is some consecutive segment of elements of the array.

You have to help Kolya and change his array in such a way that it doesn’t contain any subsegments with the sum 0. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, 0, any by absolute value, even such a huge that they can’t be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya’s array in such a way that the resulting array doesn’t contain any subsegments with the sum 0.

Input
The first line of the input contains one integer n (2≤n≤200000) — the number of elements in Kolya’s array.

The second line of the input contains n integers a1,a2,…,an (−109≤ai≤109,ai≠0) — the description of Kolya’s array.

Output
Print the minimum number of integers you have to insert into Kolya’s array in such a way that the resulting array doesn’t contain any subsegments with the sum 0.

Examples
inputCopy
4
1 -5 3 2
outputCopy
1
inputCopy
5
4 -2 3 -9 2
outputCopy
0
inputCopy
9
-1 1 -1 1 -1 1 1 -1 -1
outputCopy
6
inputCopy
8
16 -5 -11 -15 10 5 4 -4
outputCopy
3
Note
Consider the first example. There is only one subsegment with the sum 0. It starts in the second element and ends in the fourth element. It’s enough to insert one element so the array doesn’t contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer 1 between second and third elements of the array.

There are no subsegments having sum 0 in the second example so you don’t need to do anything.

solution

/*
题意：
+ 给出一个数组，求最少需要插入几个数，可以使得数组不存在为0的子段。
思路：
+ 因为什么都可以插，所以插入正无穷，一定能分隔，等价于找区间设立断点。
+ 若区间[l,r]和为零，则其前缀和s[r]-s[l-1]=0时，所以再用set维护一下。
+ 断点等价于前面的前缀和清空不算，注意0的特判。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
LL a[maxn];
int main(){
	ios::sync_with_stdio(false);
	int n;  cin>>n;
	int ans = 0;
	set<LL>se;  se.insert(0);
	for(int i = 1; i <= n; i++){
		int x;  cin>>x;  
		a[i] = x;  a[i] += a[i-1];
		if(!se.count(a[i]))se.insert(a[i]);
		else{
			ans++;
			se.clear();
			a[i] = x;
			se.insert(a[i]);
			se.insert(0);
		}
	}
	cout<<ans<<"\n";
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/113486072