GitHub 源文件 Markdown English

端倪发生器¶

预估时间限制：2.5 秒。内存限制：1024 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

“老PJ阴啊，这一定发生了什么端倪！”

读者可以自行证明，2018年的 UNR Day 2 T3 是一个长度为 \(N\) 的序列，每个元素都是绝对值不超过 \(10^9\) 的整shun。

老ZY发现，一段和为零的区间能够发生端倪。如果有足够多的端倪，就能制造出端倪发生器。我们把一段区间的端倪强度定义为：其中所有和为零的子区间的长度之和。

现在，老ZY要在这个序列中选择 \(M\) 个区间，询问每个区间的端倪强度。为了防止你离线处理，询问使用上一次的答案加密；第一次询问前，上一次答案视为零。

形式化问题描述¶

给定长度为 \(N\) 的整数序列 \(a_1,\ldots,a_N\) .回答 \(M\) 次询问。对于解码后的闭区间 \([l,r]\) ，答案为

\[ \sum_{l\le s\le t\le r}\left[\sum_{j=s}^{t}a_j=0\right](t-s+1). \]

方括号表示条件成立时为一，否则为零。即把询问区间内所有非空、和为零的子区间长度相加。

令 last 为上一询问的答案，第一次询问前为零。每次读到原始整数 \(u,v\) 后，计算

\[ x=((u\mathbin{\mathrm{XOR}}\mathrm{last})\bmod N)+1,\qquad y=((v\mathbin{\mathrm{XOR}}\mathrm{last})\bmod N)+1, \]

再令 \(l=\min(x,y)\) 、\(r=\max(x,y)\) .XOR 为非负整数的按位异或，使用完整的上一答案，不截断为三十二位。输出本次答案后更新 last .询问不修改序列，答案不取模。

输入格式¶

第一行两个整数 \(N,M\) .第二行 \(N\) 个整数 \(a_1,\ldots,a_N\) .接下来 \(M\) 行，每行两个尚未解码的整数 \(u,v\) .

输出格式¶

输出 \(M\) 行，每行一个整数，依次表示各询问的答案。

样例¶

样例 1¶

输入¶

输出¶

8
0

样例 2¶

输入¶

7 2
0 0 0 0 0 0 0
0 6
0 6

输出¶

84
56

样例 3¶

输入¶

1 2
0
0 0
1000000000 1000000000

输出¶

1
1

样例解释¶

第一组第一次询问为 \([1,4]\) ，零和区间是 \([1,2]\) 、\([3,4]\) 、\([1,4]\) ，长度和为八。随后 last=8 ，第二次解码为 \([1,1]\) ，答案零。第二组先查询七个零，答案为 \(7\times8\times9/6=84\) ；下一次解码为 \([1,6]\) ，答案为五十六。第三组始终查询唯一的零。

数据范围与保证¶

\(1\le N,M\le10^5\) , \(|a_i|\le10^9\) , \(0\le u,v\le10^9\) .

分值比例	额外条件
100%	无额外条件