[NOIP2025] 序列询问

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

有 $q$ 次询问。第 $j$ 次询问给出 $L_j,R_j$（$1\le L_j\le R_j\le n$）。对这次询问，称区间 $[l,r]$ 是「极好的」，当且仅当它的长度在 $[L_j,R_j]$ 内，即

$$L_j\le r-l+1\le R_j.$$

区间 $[l,r]$ 的权值为 $\sum_{t=l}^{r}a_t$。对于每个位置 $i=1,2,\ldots,n$，令

$$k_i=\max_{1\le l\le i\le r\le n} \left\{\sum_{t=l}^{r}a_t\ \middle|\ L_j\le r-l+1\le R_j\right\}.$$

你需要对每次询问计算

$$\bigoplus_{i=1}^{n}\left((i\times k_i)\bmod 2^{64}\right),$$

其中 $\oplus$ 表示二进制按位异或。对于任意整数 $x$，$x\bmod 2^{64}$ 表示唯一满足 $0\le x'<2^{64}$ 且 $x'\equiv x\pmod{2^{64}}$ 的非负整数 $x'$。

输入格式

第一行包含一个正整数 $n$，表示序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，第 $j$ 行包含两个正整数 $L_j,R_j$。

输出格式

对每次询问输出一行一个非负整数，表示上述异或值。

样例输入

4
2 4 -5 1
3
1 2
3 4
1 4

样例输出

18446744073709551603
8
4

样例解释

对于第一次询问：

• 包含位置 $1$ 的合法区间 $[1,1]$、$[1,2]$ 的权值分别为 $2,6$；
• 包含位置 $2$ 的合法区间 $[1,2]$、$[2,2]$、$[2,3]$ 的权值分别为 $6,4,-1$；
• 包含位置 $3$ 的合法区间 $[2,3]$、$[3,3]$、$[3,4]$ 的权值分别为 $-1,-5,-4$；
• 包含位置 $4$ 的合法区间 $[3,4]$、$[4,4]$ 的权值分别为 $-4,1$。

因此 $k_1=6,k_2=6,k_3=-1,k_4=1$。

题包还提供了另外七组公开样例。

数据范围

对于所有测试数据：

• $1\le n\le 5\times 10^4$；
• $1\le q\le 1024$；
• $|a_i|\le 10^5$；
• $1\le L_j\le R_j\le n$。

部分测试满足以下一项性质：$L_j=R_j$；$R_j\le 32$；$L_j\le 16$ 且 $R_j\ge n-1000$；$L_j>n/2$；或 $L_j>n/4$。

来源与许可

本题为 CCF NOIP 2025 第四题「序列询问（query）」。题面与测试数据来自 NOI 官网发布页 与 官方评测数据附件，按 CC BY-NC 4.0 使用。原赛制使用 query.in / query.out 文件输入输出；本平台等价适配为标准输入输出。