A92618.[NOIP2025] 序列询问

NOIP2025 T4

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

有 $q$ 次询问，其中第 $j$ ($1 \le j \le q$) 次询问将会给出 $L_j, R_j$ ($1 \le L_j \le R_j \le n$)。定义区间 $[l, r]$ ($1 \le l \le r \le n$) 是极好的，当且仅当区间 $[l, r]$ 的长度在 $[L_j, R_j]$ 内，即 $L_j \le r - l + 1 \le R_j$。定义区间 $[l, r]$ ($1 \le l \le r \le n$) 的权值为 $\sum_{i=l}^{r} a_i$。对于所有 $i = 1, 2, \ldots, n$，求出所有包含 $i$ 的极好区间的最大权值，即 $\max_{1 \le l \le i \le r \le n} \{ \sum_{i=l}^{r} a_i \mid L_j \le r - l + 1 \le R_j \}$。

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

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

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

输入的第 $j + 3$ ($1 \le j \le q$) 行包含两个正整数 $L_j, R_j$，表示第 $j$ 次询问。

对于每次询问，设包含 $i$ ($1 \le i \le n$) 的极好区间的最大权值为 $k_i$，输出一行一个非负整数，表示 $\bigoplus_{i=1}^{n} \left( (i \times k_i) \bmod 2^{64} \right)$，其中 $\oplus$ 表示二进制按位异或。注意：对于任意整数 $x$，存在唯一的非负整数 $x'$ 满足 $x' \equiv x \pmod{2^{64}}$ 且 $0 \le x' \le 2^{64} - 1$，则记 $x \bmod 2^{64} = x'$。

【数据范围】

对于所有测试数据，均有：

• $1 \le n \le 5 \times 10^4$，$1 \le q \le 1,024$；
• 对于所有 $1 \le i \le n$，均有 $|a_i| \le 10^5$；
• 对于所有 $1 \le j \le q$，均有 $1 \le L_j \le R_j \le n$。

测试点编号	$n \le$	$q \le$	特殊性质
1	$10^3$	1	无
2,3	3,000	50	无
4	$10^4$	128	无
5	$3 \times 10^4$	512	无
6,7	$5 \times 10^4$	1,024	A
8～10	$5 \times 10^4$	512	B
11,12	$5 \times 10^4$	512	C
13	$5 \times 10^4$	1,024	D
14,15	$5 \times 10^4$	1,024	E
16～20	$5 \times 10^4$	1,024	无

特殊性质 A：对于所有 $1 \le j \le q$，均有 $L_j = R_j$。

特殊性质 B：对于所有 $1 \le j \le q$，均有 $R_j \le 32$。

特殊性质 C：对于所有 $1 \le j \le q$，均有 $L_j \le 16$ 且 $R_j \ge n - 1000$。

特殊性质 D：对于所有 $1 \le j \le q$，均有 $L_j > n/2$。

特殊性质 E：对于所有 $1 \le j \le q$，均有 $L_j > n/4$。