AT_joi2026final_a 伝説の団子食通 (Legendary Dango Eater)

Bitaro 买了一串很长的饺子。这串饺子可以用 $N$ 个正整数 $A_1, A_2, \cdots, A_N$ 来表示。对于每个整数 $i$ 满足 $0 \leq i \leq N$，定义 $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$）由整数 $L_j$ 和 $R_j$ 描述，满足 $1 \leq L_j \leq R_j \leq N$。在该计划中，他将吃下从第 $(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$ 行输出第 $j$ 个计划下 Bitaro 最多能感到满意的次数。 ---

### 子任务 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$ 分）无额外限制。 --- ### 样例解释 1 对于第一个计划，Bitaro 会吃掉从第 1 个饺子到第 $12$ 个饺子。从上往下每口只吃 1 个饺子，可以让他感到满意 $7$ 次。不可能让他感到满意 $8$ 次或以上。所以输出 $7$。 对于第二个计划，Bitaro 会吃第 3 个到第 9 个饺子。从上往下每口只吃 1 个饺子，可以让他感到满意 $2$ 次。不可能让他感到满意 $3$ 次或以上，所以输出 $2$。 此样例输入满足所有子任务的限制。 --- ### 样例解释 2 本样例与样例输入 1 只有 $K$ 的值不同。 对于第一个计划，Bitaro 采用如下的 4 口吃法，可以感到满意 2 次： - 第一口吃第 1 个到第 5 个饺子。甜饺子数为 4，辣饺子数为 1，Bitaro 满意。 - 第二口只吃第 6 个饺子。甜饺子数为 0，辣饺子数为 1，Bitaro 不满意。 - 第三口吃第 7 个到第 9 个。甜饺子数为 0，辣饺子数为 3，Bitaro 不满意。 - 第四口吃第 10 到第 12 个饺子。甜饺子数为 3，辣饺子数为 0，Bitaro 满意。 Bitaro 最多只能满意 2 次，所以输出 2。 对于第二个计划，无论怎么吃，Bitaro 都无法满意至少一次，所以输出 0。 此样例输入满足子任务 1、3、4、5、6 的所有限制。 --- ### 样例解释 3 此样例输入满足子任务 1、4、5、6 的所有限制。 ### 约束条件 - $1 \leq N \leq 500\,000$。 - $1 \leq Q \leq 500\,000$。 - $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)$。 - 所有给定的数均为整数。 由 ChatGPT 5 翻译