← 返回题目列表

Codeforces · 1933/E

E. 乌龟与兔子竞赛:最佳训练

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

艾萨克开始训练。有 $$$n$$$ 可用跑道,第 $$$i$$$ 跑道 ($$$1 \le i \le n$$$) 由 $$$a_i$$$ 等长部分组成。

给定一个整数$$$u$$$ ($$$1 \le u \le 10^9$$$),完成每个部分可以使Isaac的能力增加一定的值,描述如下:

- 完成 $$$1$$$-st 部分后,Isaac 的表现提高了 $$$u$$$。
- 完成 $$$2$$$-nd 部分后,Isaac 的表现提高了 $$$u-1$$$。
- 完成 $$$3$$$-rd 部分后,艾萨克的表现提高了 $$$u-2$$$。
- $$$\ldots$$$
- 完成第 $$$k$$$ 部分 ($$$k \ge 1$$$) 会使 Isaac 的表现提高 $$$u+1-k$$$。 ($$$u+1-k$$$ 值可以为负数,这意味着完成额外的部分会降低 Isaac 的表现。)

还给你一个整数$$$l$$$。您必须选择一个整数 $$$r$$$,使得 $$$l \le r \le n$$$ 和 Isaac 将完成每个曲目 $$$l, l + 1, \dots, r$$$ 的每个部分(即总共 $$$\sum_{i=l}^r a_i = a_l + a_{l+1} + \ldots + a_r$$$ 部分)。

回答以下问题:您可以选择的最佳 $$$r$$$ 是什么,以最大可能提高 Isaac 的性能?

如果存在多个 $$$r$$$ 可以最大化 Isaac 性能的提升,则输出最小的 $$$r$$$。

为了增加难度,您需要回答 $$$q$$$ $$$l$$$ 和 $$$u$$$ 不同值的问题。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^4$$$)。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$)。

接下来的 $$$q$$$ 行每行包含两个整数 $$$l$$$ 和 $$$u$$$ ($$$1 \le l \le n, 1 \le u \le 10^9$$$) - 每个查询的描述。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 整数:第 $$$i$$$ 个整数包含第 $$$i$$$ 查询的最佳 $$$r$$$ 。如果有多个解,则输出最小的一个。

示例

输入 #1

5
6
3 1 4 1 5 9
3
1 8
2 7
5 9
1
10
1
1 1
9
5 10 9 6 8 3 10 7 3
5
8 56
1 12
9 3
1 27
5 45
5
7 9 2 5 2
10
1 37
2 9
3 33
4 32
4 15
2 2
4 2
2 19
3 7
2 7
10
9 1 6 7 6 3 10 7 3 10
5
10 43
3 23
9 3
6 8
5 14

输出 #1

3 4 5 
1 
9 2 9 4 9 
5 2 5 5 5 2 4 5 4 2 
10 6 9 7 7

注意

对于第一个测试用例中的 $$$1$$$-st 查询:

- 通过选择 $$$r = 3$$$,Isaac 总共完成 $$$a_1 + a_2 + a_3 = 3 + 1 + 4 = 8$$$ 部分,因此他的性能提升为 $$$u+(u-1)+\ldots+(u-7)=8+7+6+5+4+3+2+1 = 36$$$。
- 通过选择 $$$r = 4$$$,Isaac 总共完成了 $$$a_1 + a_2 + a_3 + a_4 = 3 + 1 + 4 + 1 = 9$$$ 部分,因此他的性能提升为 $$$u+(u-1)+\ldots+(u-8)=8+7+6+5+4+3+2+1+0 = 36$$$。

两种选择都能获得最佳的性能提升,但我们希望选择最小的$$$r$$$。所以我们选择$$$r = 3$$$。

对于第一个测试用例中的 $$$2$$$-nd 查询,通过选择 $$$r = 4$$$,Isaac 总共完成了 $$$a_2 + a_3 + a_4 = 1 + 4 + 1 = 6$$$ 部分,因此他的性能提升为$$$u+(u-1)+\ldots+(u-5)=7+6+5+4+3+2 = 27$$$。这是性能的最佳提升。

对于第一个测试用例中的 $$$3$$$-rd 查询:

- 通过选择 $$$r = 5$$$,Isaac 总共完成 $$$a_5 = 5$$$ 部分,因此他的性能提升为 $$$u+(u-1)+\ldots+(u-4)=9+8+7+6+5 = 35$$$。
- 通过选择 $$$r = 6$$$,Isaac 总共完成了 $$$a_5 + a_6 = 5 + 9 = 14$$$ 部分,因此他的性能提升为$$$u+(u-1)+\ldots+(u-13)=9+8+7+6+5+4+3+2+1+0+(-1)+(-2)+(-3)+(-4) = 35$$$。

两种选择都能获得最佳的性能提升,但我们希望选择最小的$$$r$$$。所以我们选择$$$r = 5$$$。

因此第一个测试用例的输出是 $$$[3, 4, 5]$$$。