1426D Non-zero Segments

Description

Analysis

题意概述

给定一个长度为 $n$ 的正整数序列 $(2\le n\le 2\times 10^5)$ $a_i$（$-10^9\le a_i\le 10^9$，$a_i\ne 0$）

求至少需要插入多少个数（可以为 $R$ 上的任意大小的实数），使得该序列任意子区间的和不为 $0$

分析1

联系到前缀和思想，子区间和 $Su{m}_{l,r}$ 可以表示为 $S_r-S_{l-1}$

则对于子区间和 $Su{m}_{l,r}=0$ 的情形，即等价于 $S_r=S_{l-1}$，以及 $l=1,S_r=0$ 的情形

相对原始的想法：对前缀和数组判重，以及判断 $S_i=0$ 的元素的个数

性质

若在 $i$ 处插入一个数 $x$，将会使得前缀和序列 $S_i\to S_n$ 均 $+x$

分析2

对于 $i\to n$，其相对大小不变

例：$...,x,-1,1$：插入后，$S_{i+1}\ne S_{i+2}$，但 $-1+1=0$由此，不能直接维护整个序列的前缀和数组，而是应当维护当前段的前缀和（即截止判重时的一段数，此时，该前缀和更新为当前位置被判重的数），然后沿用判重操作同时，插入后的前一段已经不影响后一段的结果（插入一个近乎无穷大的数，后一段的前缀和必然远大于前一段，不可能相等；同时计算机也不支持这样近乎无穷大的数），因此可以将用于判重的数据结构清空

算法流程

维护当前段的前缀和 $cur$，并使用 $set$ 或 $unordered\_set$ 维护当前出现过的 $cur$ 的值

（可以将 $0$ 提前插入，规避特判，简化代码）

每当出现重复的值，则更新需要插入的数的个数 $ans$，并清空 $set$ 或 $unordered\_set$ ，将 $cur$ 更新为 $a_i$，再将 $0$ 和 $a_i$ 插入对应的数据结构（”性质“中对当前段的分析）

Code

#include <iostream> #include <cstring> #include <algorithm> #include <unordered_set> #define LL int64_t using namespace std; constexpr const int N = 2e5 + 10; int n, ans, a[N]; LL cur; unordered_set<LL> S; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; S.insert(0); for(int i = 1; i <= n; i++) { cur += a[i]; if(S.count(cur)) { ans++; S.clear(); S.insert(0); cur = a[i]; } S.insert(cur); } cout << ans; return 0; }

Summary

大概是比较常见的区间转化为前缀和的分析技巧

（印象比较深刻的是在解 AcWing 239. 奇偶游戏 的时候，如果没有此题的启发可能都做不动）

然而自己做的时候并没有分析出维护的是判重前后每一段的前缀和，直接套在整体的前缀和上做，然后来回WA

只是分析到了需要判重和判 $0$ 的时候，如果没有此题的启发可能都做不动）

$PS$：写 $cf$ 的题解感觉需要把整个问题彻底想清楚才行，光看 $ed$ 也是似懂非懂，写题解花了不少时间，不过终于把整个问题梳理清楚了）