AdditionalFile5663.zip

#5663. 「JOI 2026 Final Day1」传说中的团子美食家

标签: 传统 | 时间限制: 2500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day1 T1 「伝説の団子食通 / Legendary Dango Eater」

比太郎买了一串长长的串团子作为点心。这串团子可以用 $N$ 个正整数 $A_1, A_2, \dots, A_N$ 描述。对于满足 $0 \leq i \leq N$ 的整数 $i$，令 $s_i = A_1 + A_2 + \dots + A_i$，并规定 $s_0 = 0$。

• 串团子由 $s_N$ 个团子组成，从上到下排成一列。
• 每个团子的味道要么是甜的，要么是咸的。每个团子的味道可以表示如下：
• 当 $i$ 为满足 $1 \leq i \leq N$ 的奇数时，从上数第 $s_{i-1}+1$ 个到第 $s_i$ 个团子是甜味的。
• 当 $i$ 为满足 $1 \leq i \leq N$ 的偶数时，从上数第 $s_{i-1}+1$ 个到第 $s_i$ 个团子是咸味的。

比太郎为吃这串团子制定了 $Q$ 个计划。第 $j$ $(1 \leq j \leq Q)$ 个计划由满足 $1 \leq L_j \leq R_j \leq N$ 的整数 $L_j, R_j$ 表示，即吃掉从上数第 $s_{L_j-1}+1$ 个到第 $s_{R_j}$ 个团子。

此外，比太郎决定将这些团子分几口吃完。这里，$K$ 是代表比太郎对甜度喜好的正整数。

• 团子按从上到下的顺序食用，每个团子恰好被吃一次。
• 每一口可以吃掉串上连续的任意数量的团子。此时，如果这一口吃掉的团子中，甜味团子的数量减去咸味团子的数量所得的差值不小于 $K$，比太郎就会感到高兴。

给定串团子和计划的信息，请编写一个程序，对于每个计划，求出比太郎感到高兴的次数的最大可能值。

输入格式

第一行包含三个整数 $N,Q,K$。

第二行包含 $N$ 个空格分隔的整数 $A_{1} A_{2} \ldots A_{N}$。

接下来的 $Q$ 行，每行包含两个整数 $L_i,R_i$。

输出格式

输出共 $Q$ 行。第 $j$ $(1 \leq j \leq Q)$ 行应输出第 $j$ 个计划中比太郎感到高兴次数的最大可能值。

样例 1

输入

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

输出

7
2

对于第 $1$ 个计划，比太郎会吃掉从上数第 $1$ 个到第 $12$ 个团子。比太郎通过重复“从上往下每口吃一个团子”的操作，可以将感到高兴的次数增加到 $7$ 次。由于无法使高兴次数达到 $8$ 次或以上，因此输出 $7$。

对于第 $2$ 个计划，比太郎会吃掉从上数第 $3$ 个到第 $9$ 个团子。比太郎通过重复“从上往下每口吃一个团子”的操作，可以将感到高兴的次数增加到 $2$ 次。由于无法使高兴次数达到 $3$ 次或以上，因此输出 $2$。

此样例满足所有子任务的限制。

样例 2

输入

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

输出

2
0

与样例 $1$ 仅在 $K$ 的值上有所不同。

对于第 $1$ 个计划，比太郎通过像下面这样分四口吃团子，可以将感到高兴的次数增加到 $2$ 次：

• 第一口吃掉从上数第 $1$ 个到第 $5$ 个团子。因为甜味团子有 $4$ 个，咸味团子有 $1$ 个，差值为 $4-1=3 \geq 3$，所以比太郎感到高兴。
• 第二口仅吃掉从上数第 $6$ 个团子。因为甜味团子有 $0$ 个，咸味团子有 $1$ 个，所以比太郎不高兴。
• 第三口吃掉从上数第 $7$ 个到第 $9$ 个团子。因为甜味团子有 $0$ 个，咸味团子有 $3$ 个，所以比太郎不高兴。
• 第四口吃掉从上数第 $10$ 个到第 $12$ 个团子。因为甜味团子有 $3$ 个，咸味团子有 $0$ 个，所以比太郎感到高兴。

由于无法使高兴次数达到 $3$ 次或以上，因此输出 $2$。

对于第 $2$ 个计划，比太郎无论如何进食都无法感到高兴 $1$ 次或以上，因此输出 $0$。

此样例满足子任务 $1, 3, 4, 5, 6$ 的限制。

样例 3

输入

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

输出

3
2
1
1

此样例满足子任务 $1, 4, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 500000$。
• $1 \leq Q \leq 500000$。
• $1 \leq K \leq 10^{14}$。
• $1 \leq A_{i} \leq 10^9$ $(1 \leq i \leq N)$。
• $1 \leq L_{j} \leq R_{j} \leq N$ $(1 \leq j \leq Q)$。
• 所有输入值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$6$	$Q \leq 10$
$2$	$5$	$K \leq 2$
$3$	$18$	$K \leq 10$
$4$	$27$	$A_{1}+A_{2}+\cdots+A_{N} \leq 500000$
$5$	$17$	$N \leq 200000, Q \leq 200000$
$6$	$27$	无附加限制