【题解】CF1426D Non-zero Segments

\(\text{Solution:}\)

若\([l,r]\)子段和是\(0,\)则\(sum[r]=sum[l-1].\)

于是我们可以考虑维护当前哪一个前缀和出现过。对于区间\([l,r]\)若其子段和为\(0\)则在\(r-1\)的地方插入一个\(+\infty\)即可。

初始化要把\(0\)赋值为出现过。

#include<bits/stdc++.h>

using namespace std;

int n,a[500010];

map<long long,bool>mp;

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i)scanf("%d",&a[i]);

	mp[0]=true;

	long long s=0;

	int ans=0;

	for(int i=1;i<=n;++i){

		s+=a[i];

		if(mp[s]){

			ans++;

			mp.clear();

			mp[0]=true;

			s=a[i];

		}

		mp[s]=true;

	}

	cout<<ans<<endl;

	return 0;

}

```cpp

巴特西

【题解】CF1426D Non-zero Segments

最新文章

热门文章