P15939 [JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater

Bitaro 买了一长串团子作为零食。这串团子可以用 $N$ 个正整数 $A_1, A_2, \cdots, A_N$ 表示如下。对于每个满足 $0 \leq i \leq N$ 的整数 $i$，令 $s_i = A_1 + A_2 + \cdots + 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$ 个团子是辣的。 在吃这串团子时，Bitaro 制订了 $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}$ 个团子。 此外，在吃这串团子时，Bitaro 决定按照以下方式将其分成几口来吃。这里，$K$ 是一个正整数，代表 Bitaro 对甜度的偏好。 - 他从上到下吃团子，并且每个团子恰好被吃一次。 - 在一口中，他可以吃掉串上任意正数个连续的团子。如果在那一口吃掉的团子中，甜团子的数量减去辣团子的数量至少为 $K$，那么 Bitaro 就会感到满足。 给定关于这串团子和计划的信息，编写一个程序，对于每个计划，计算 Bitaro 能够感到满足的最大可能次数。

从标准输入读取以下数据。 > $N$ $Q$ $K$\ > $A_1$ $A_2$ $\cdots$ $A_N$\ > $L_1$ $R_1$\ > $L_2$ $R_2$\ > $\vdots$\ > $L_Q$ $R_Q$

向标准输出写入 $Q$ 行。在第 $j$ 行（$1 \leq j \leq Q$），输出在第 $j$ 个计划中 Bitaro 能够感到满足的最大次数。

### 样例 1 对于第一个计划，Bitaro 吃掉从上往下数第 $1$ 到第 $12$ 个团子。通过反复从顶部每口恰好吃一个团子，Bitaro 可以感到满足 $7$ 次。因为不可能让他感到满足 $8$ 次或更多，所以你应该输出 $7$。 对于第二个计划，Bitaro 吃掉从上往下数第 $3$ 到第 $9$ 个团子。通过反复从顶部每口恰好吃一个团子，Bitaro 可以感到满足 $2$ 次。因为不可能让他感到满足 $3$ 次或更多，所以你应该输出 $2$。 这个样例输入满足所有子任务的约束条件。 ### 样例 2 这与样例输入 $1$ 仅在 $K$ 的值上有所不同。 对于第一个计划，Bitaro 可以通过分以下四口吃团子来感到满足 $2$ 次。 - 第一口，他吃掉从上往下数第 $1$ 到第 $5$ 个团子。由于甜团子的数量为 $4$，辣团子的数量为 $1$，Bitaro 感到满足。 - 第二口，他只吃掉从上往下数第 $6$ 个团子。由于甜团子的数量为 $0$，辣团子的数量为 $1$，Bitaro 没有感到满足。 - 第三口，他吃掉从上往下数第 $7$ 到第 $9$ 个团子。由于甜团子的数量为 $0$，辣团子的数量为 $3$，Bitaro 没有感到满足。 - 第四口，他吃掉从上往下数第 $10$ 到第 $12$ 个团子。由于甜团子的数量为 $3$，辣团子的数量为 $0$，Bitaro 感到满足。 因为不可能让他感到满足 $3$ 次或更多，所以你应该输出 $2$。 对于第二个计划，Bitaro 不可能以让他至少感到满足一次的方式吃团子，所以你应该输出 $0$。 这个样例输入满足子任务 $1,3,4,5,6$ 的约束条件。 ### 样例 3 这个样例输入满足子任务 $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 500\,000$。 5. (17 分) $N \leq 200\,000$, $Q \leq 200\,000$。 6. (27 分) 无附加限制。