qdez信竞队

[rrzhs]

欢迎加入青岛二中信息竞赛队
学校oj https://qdezoj.cpolar.cn/d/tigao/ (账号可到仁智楼三楼信息技术组报名领取)

[__ZeroEgg__]

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。

过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

[zshebjtzs]

# P14638 [NOIP2025] 序列询问

## 题目背景

额外提供了 1 秒的时限。

## 题目描述

给定一个长度为 $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

### 输入 #1

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

### 输出 #1

```
18446744073709551603
8
4
```

## 说明/提示

### 【样例 1 解释】

对于第 $1$ 次询问：
- 包含 $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$。

对于第 2 次询问，$k_1 = 2$，$k_2 = 2$，$k_3 = 2$，$k_4 = 2$。

对于第 3 次询问，$k_1 = 6$，$k_2 = 6$，$k_3 = 2$，$k_4 = 2$。

### 【样例 2】

见选手目录下的 `query/query2.in` 与 `query/query2.ans`。

该样例满足测试点 $2,3$ 的约束条件。

### 【样例 3】

见选手目录下的 `query/query3.in` 与 `query/query3.ans`。

该样例满足测试点 $4$ 的约束条件。

### 【样例 4】

见选手目录下的 `query/query4.in` 与 `query/query4.ans`。

该样例满足测试点 $6,7$ 的约束条件。

### 【样例 5】

见选手目录下的 `query/query5.in` 与 `query/query5.ans`。

该样例满足测试点 $8 \sim 10$ 的约束条件。

### 【样例 6】

见选手目录下的 `query/query6.in` 与 `query/query6.ans`。

该样例满足测试点 $11,12$ 的约束条件。

### 【样例 7】

见选手目录下的 `query/query7.in` 与 `query/query7.ans`。

该样例满足测试点 $13$ 的约束条件。

### 【样例 8】

见选手目录下的 `query/query8.in` 与 `query/query8.ans`。

该样例满足测试点 $16 \sim 20$ 的约束条件。

### 【数据范围】

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

- $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$。

::cute-table{tuack}

测试点编号	$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 \sim 10$	^	$512$	B
$11,12$	^	^	C
$13$	^	$1{,}024$	D
$14,15$	^	^	E
$16 \sim 20$	^	^	无

特殊性质 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$。

[__ZeroEgg__]

注意到，论坛似乎不支持LaTeX渲染导致zshbjtzs在M↓整篇题目时出现了一堆美金符号/gt

[cloudwalk]

好的现在已经可以渲染LaTeX了 至于md应该需要新发帖才能渲染出来