D. Non-zero Segments

发布时间 2023-04-21 16:34:21作者: magicat

D. Non-zero Segments

过程:手玩样例发现,前缀和中出现相同值即为区间和为0

由前缀和公式\(S_i = S_{i - 1} + A_i\)可以知道,区间\([l,r]\)满足题意即为\(S_r = S_{l-1}\),对于每个区间插入个巨大的数,让区间\([1, r-1]\)的前缀和都作废,注意对0处理

even such a huge that they can't be represented in most standard programming languages

ll n, s[N], ans; 
set<ll> S;
void solve()
{   
	cin>>n;
	for(int i = 1; i <= n; i++)
		cin>>s[i];
	S.insert(0);
	for(int i = 1; i <= n; i++)
	{
		s[i] += s[i - 1];
		if(S.count(s[i]))
		{	
			ans++;
			S.clear();
			S.insert(0);
			s[i] -= s[i - 1];
		}
		S.insert(s[i]);
	}
	cout<<ans<<endl;

    return;
}