分数: 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).
- 给定值均为整数。
子任务
- (6 点) Q \leq 10.
- (5 点) K \leq 2.
- (18 点) K \leq 10.
- (27 点) A_1 + A_2 + \cdots + A_N \leq 500\,000.
- (17 点) N \leq 200\,000, Q \leq 200\,000.
- (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.