← 返回题目列表

Codeforces · 2206/E

E. 并行求和

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

给你两个整数 $$$n$$$ 和 $$$m$$$。对于 $$$n$$$ 整数序列 $$$A=(a_1, a_2, \ldots, a_n)$$$, 并行求和 是 $$$n-m+1$$$ 整数 $$$s_1, s_2, \ldots, s_{n-m+1}$$$ 定义为 $$$s_i = a_i + a_{i+1} + \ldots + a_{i+m-1}$$$ 对于每个 $$$i$$$ ($$$1 \leq i \leq n-m+1$$$)。

给定的值为 $$$s_1, s_2, \ldots, s_{n-m+1}$$$。您的任务是回答 $$$q$$$ 查询,如下所述。在第 $$$j$$$ 查询中,给定两个整数 $$$l_j$$$ 和 $$$r_j$$$,并要求你在所有序列 $$$A=(a_1, a_2, \ldots, a_n)$$$ 的 $$$n$$$ 整数(可能为负),使得 $$$s_1, s_2, \ldots, s_{n-m+1}$$$ 是 $$$A$$$ 的并行和。或者判断这个值是否可以任意小。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 200\,000$$$)。

第二行包含 $$$n-m+1$$$ 整数 $$$s_1, s_2, \ldots, s_{n-m+1}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$)。

第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 100\,000$$$)。

接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$)。

输出

输出 $$$q$$$ 行。第 $$$j$$$ 行应包含 $$$\max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j})$$$ 的最小可能值。如果该值可以任意小,则输出 无界 相反, 。

示例

输入
复制

8 4
4 -4 2 6 5
4
3 7
4 6
1 8
2 5

输出
复制

2
unbounded
4
-1

注意

示例输入/输出 #1 的说明

对于第一个查询,取 $$$A = (9, -4, -3, 2, 1, 2, 1, 1)$$$。根据要求,$$$A$$$ 的并行和为 $$$(4, -4, 2, 6, 5)$$$。那么 $$$\max(a_3, \ldots, a_7) = \max(-3, 2, 1, 2, 1) = 2$$$。可以证明 $$$2$$$ 是最小的可能值。

对于第二个查询,您可以将该值设置为任意小。

对于第三个查询,取 $$$A = (4, -3, 0, 3, -4, 3, 4, 2)$$$。那么 $$$\max(4, -3, 0, 3, -4, 3, 4, 2) = 4$$$,这是最小的可能值。