CF1748C Zero-Sum Prefixes

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;  
}