UPD 23.10.3 更新的对思路的描述，以及代码。

思路

对于每一个 \(a_i = 0\)，如果我们将它变为 \(x\)，都可以直接将 \(i \sim n\) 位置上的前缀和加 \(x\)。

设 \(a_j\) 是 \(a_i\) 后第一个 \(0\)，那么，在 \(j\) 时同样有上述规律。

所以，我们只需在 \(i\) 时考虑，\(i \sim (j - 1)\) 的贡献。

因为我们想尽可能的使 \(s_x = 0\) 的数量更多，所以我们就要让 \(a_i\) 修改为在 \(i \sim (j - 1)\) 中 \(s_k\) 出现次数最多的元素的相反数。

特别的，如果 \(i\) 后没有任意一个位置 \(j\) 为 \(0\)，那么，考虑 \(i \sim n\) 即可。（直接加一个 \(n + 1\) 的哨兵即可）

因为 \(i\) 的修改对 \(1 \sim (i - 1)\) 的前缀和无关，所以只需枚举 \(i \sim (j - 1)\) 的位置，保证了更新的位置总和是 \(\Theta(n)\)，然后还需要用一个 map 维护前缀和的出现次数。

综上，时间复杂度为 \(\Theta(n \log n)\)。

code

#include <bits/stdc++.h>
#define re register
#define ll long long

using namespace std;

const int N = 2e5 + 10;
int T,n;
int arr[N];
ll s[N];

inline int read(){
	int r = 0,w = 1;
	char c = getchar();
	while (c < '0' || c > '9'){
		if (c == '-') w = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		r = (r << 1) + (r << 3) + (c ^ 48);
		c = getchar();
	}
	return r * w;
}

int main(){
	T = read();
	while (T--){
		int ans = 0,len = 0;
		vector<int> v;
		n = read();
		for (re int i = 1;i <= n;i++) arr[i] = s[i] = 0;
		for (re int i = 1;i <= n;i++){
			arr[i] = read();
			s[i] = s[i - 1] + arr[i];
			if (!arr[i]){
				len++;
				v.push_back(i);
			}
		}
		v.push_back(n + 1);
		for (re int i = 1;i < v.front();i++){
			if (!s[i]) ans++;
		}
		for (re int x = 0;x < len;x++){
			unordered_map<ll,int> vis;
			int Max = 0;
			for (re int i = v[x];i < v[x + 1];i++){
				vis[s[i]]++;
				Max = max(Max,vis[s[i]]);
			}
			ans += Max;
		}
		printf("%d\n",ans);
	}
	return 0;
}