4098 G-CAT

题面

内容

有一个长度为 $n$ 的序列，第 $i$ 个位置的值为 $c_i$。

$q$ 次询问，每次给定 $1 \leq l \leq r \leq n$，考虑子序列 $c_l, c_{l+1}, \cdots, c_{r}$，你需要选出若干个互不相交的区间，满足每个区间的元素之和为 0。要求最大化选择区间的数量，求出你可以选出多少个区间。

输入

输入的第一行包含一个整数 $n$。

接下来一行，包含 $n$ 个整数 $c_1,c_2,\cdots, c_n$。

接下来一行，包含一个整数 $q$。

接下来 $q$ 行，每行两个整数 $l, r$，描述一组询问。

输出

对于每组询问，输出一行一个整数，表示答案。

样例1

输入

10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9

输出

4
2
2

提示

对于 $20\%$ 的数据，$1 \leq n,q \leq 5\,000$。

对于 $50\%$ 的数据，$1 \leq n,q \leq 10^5$。

另有 $20\%$ 的数据，$-10 \leq c_i \leq 10$。

对于 $100\%$ 的数据，$1 \leq n,q \leq 4 \times 10^5$，$-10^9 \leq c_i \leq 10^9$，$1 \leq l_i \leq r_i \leq n$。

思路

$i$表示最后一个选择的区间的右端点，

$f_i$表示最多能选的区间，优先选短的区间，

对i而言，找到一个最大的j使得区间和为0，即右端点和左端点左边的前缀和相同

记录一个last为上次和i前置和相同的点的位置，

i一定从j-1转移过来么？

不一定，因为上一段不一定以j-1结尾

那就把j之前的区间的f值取个max来更新$f_i$

$f_i=max(f_j)+1$

那么q次询问就需要通过数据结构来优化复杂度

以每个i结尾的区间最多只有一个有意义，即最小的，

那么总共就有n个区间有意义，将它预处理出来，然后建树

以i结尾的区间for一遍就可以通过last维护最小的这个区间

选完一个区间后就可以选右端点最小的区间

所以说选完以后选下一个区间是一个固定的过程

预处理

这样出来以后就是一棵树

第一个的是左端点大于l右端点最小的区间

然后一直走直到超出r，

倍增求解就可以了。