CF2033D.Kousuke's Assignment

在和 Sakurako 一起旅行后，Kousuke 因为忘记了他的编程作业而感到非常害怕。在这次作业中，老师给了他一个长度为 $n$ 的整数数组 $a$，并要求他计算数组 $a$ 中不重叠的区间的最大数量，使得每个区间都是“美丽的”。

如果区间 $[l, r]$ 满足 $a_l + a_{l+1} + \dots + a_{r-1} + a_r = 0$，则称该区间为“美丽的”。

对于给定的数组 $a$，你的任务是计算不重叠美丽区间的最大数量。

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例包含两行。

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。
• 第二行包含 $n$ 个整数 $a_i$（$-10^5 \le a_i \le 10^5$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示不重叠美丽区间的最大数量。

由 ChatGPT 4.1 翻译