P11406 [RMI 2020] 零和 / Sum Zero

译自 [8th Romanian Master of Informatics, RMI 2020](https://rmi.lbi.ro/rmi_2020/) D2T1。$\texttt{0.6s,\textcolor{red}{20M}}$。 **请注意本题非同寻常的空间限制。**

给定长度为 $N$ 的数列 $c_1,\cdots,c_N$。 $Q$ 次询问给定 $L,R$，求出最多能够选出多少个 $[L,R]$ 的**不交**子区间，满足每个子区间内 $c_i$ 的和均为 $0$。

第一行，一个正整数 $N$。 第二行，$N$ 个整数 $c_1,\cdots,c_N$。 第三行，一个正整数 $Q$。 接下来 $Q$ 行，每行两个正整数 $L,R$。

输出 $Q$ 行，每行一个整数表示答案。

对于 $100\%$ 的数据，保证： - $1\le N,Q\le 4\times 10^5$； - $-10^9\le c_i\le 10^9$； - $1\le L\le R\le N$。 | 子任务编号 | $N,Q\le $ | 得分 | | :--: | :--: | :--: | | $ 1 $ | $ 5\times 10^3 $ | $22$ | | $ 2 $ | $ 10^5 $ | $39$ | | $ 3 $ | $ 4\times 10^5 $ | $39$ |