← 返回题目列表

AtCoder · joi2026final_a

A. 传奇团子食者

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

比特太郎买了一串长长的饺子当零食。这个串可以表示为 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 饺子从上到下排成一列。
  • 每个饺子都是 甜蜜 or 辣。每个饺子的味道可以描述如下。
    • If i 是满足以下条件的奇数 1 \leq i \leq N,然后饺子从 (s_{i-1} + 1)-第 s_i从上往下数很甜。
    • If i 是满足的偶数 1 \leq i \leq N,然后饺子从 (s_{i-1} + 1)-第 s_i从上往下数是辣的。

吃这串饺子的时候,比特太郎做了 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- 第行 (1 \leq j \leq Q),输出 Bitaro 可以高兴的最大次数 j第一个计划。


约束

  • 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).
  • 给定值均为整数。

子任务

  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

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

示例输出 1

7
2

对于第一个计划,Bitaro 从第一个到第二个都吃饺子 12从上往下数。通过反复从顶部咬下一个饺子,Bitaro 会感到高兴 7 次。既然不可能让他高兴 8 次或更多,你应该输出 7.

对于第二个计划,Bitaro 从第三个到第三个都吃饺子。 9从上往下数。通过反复从顶部咬下一个饺子,Bitaro 会感到高兴 2 次。既然不可能让他高兴 3 次或更多,你应该输出 2.

此示例输入满足所有子任务的约束。


示例输入 2

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

示例输出 2

2
0

这与样本输入不同 1 仅在值 K.

对于第一个计划,Bitaro 可以很高兴 2 次通过吃下面四口的饺子。

  • 在第一口中,他通过 5从上面第一个饺子。由于汤圆的数量是 4 麻辣烫的数量是 1Bitaro很高兴。
  • 在第二口中,他只吃了 6从上面第一个饺子。由于汤圆的数量是 0 麻辣烫的数量是 1,Bitaro 不高兴。
  • 第三口,他吃了 7th 通过 9从上面第一个饺子。由于汤圆的数量是 0 麻辣烫的数量是 3,Bitaro 不高兴。
  • 在第四口,他吃了 10th 通过 12从上面第一个饺子。由于汤圆的数量是 3 麻辣烫的数量是 0Bitaro很高兴。

既然不可能让他高兴 3 次或更多,你应该输出 2.

对于第二个计划,Bitaro不可能以他满意的方式至少吃一次饺子,所以你应该输出 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

3
2
1
1

此示例输入满足子任务的约束 1,4,5,6.