最优训练
英文名:Turtle vs. Rabbit Race: Optimal Trainings
题目描述
Isaac 开始训练。一共有 n 条跑道,第 i 条跑道(1≤i≤n)由 ai 段长度相等的路段组成。
给定一个整数 u(1≤u≤109),每完成一段路,Isaac 的能力会增加一个特定的值:
- 完成第 1 段,能力增加 u;
- 完成第 2 段,能力增加 u−1;
- 完成第 3 段,能力增加 u−2;
- ……
- 完成第 k 段(k≥1),能力增加 u+1−k。(该值可以为负数,即多完成一段反而会降低能力。)
另外给定一个整数 l。你需要选择一个整数 r,满足 l≤r≤n,Isaac 会跑完第 l,l+1,…,r 条跑道的每一段(总共 ∑i=lrai=al+al+1+⋯+ar 段)。
问题:选择怎样的 r,才能使 Isaac 能力的增加量最大?
如果有多个 r 都能使增加量最大,输出最小的 r。
为了增加难度,你需要对 q 组不同的 (l,u) 回答上述问题。
输入格式
第一行一个整数 t(1≤t≤104),表示测试数据组数。
接下来依次给出每组数据:
- 第一行一个整数 n(1≤n≤105)。
- 第二行 n 个整数 a1,a2,…,an(1≤ai≤104)。
- 第三行一个整数 q(1≤q≤105)。
- 接下来 q 行,每行两个整数 l,u(1≤l≤n,1≤u≤109)。
输出格式
对于每组测试数据,输出一行 q 个整数:第 i 个整数表示第 i 个询问的最优 r。若答案不唯一,输出其中最小的 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
输出
3 4 5
1
9 2 9 4 9
5 2 5 5 5 2 4 5 4 2
10 6 9 7 7
说明
针对第一组数据(a=[3,1,4,1,5,9]):
- 询问 (l,u)=(1,8):选 r=3 时共跑 3+1+4=8 段,收益为 8+7+6+5+4+3+2+1=36;选 r=4 时共跑 9 段,收益为 8+7+6+5+4+3+2+1+0=36。两者并列最优,取较小的 r=3。
- 询问 (l,u)=(2,7):选 r=4 时共跑 1+4+1=6 段,收益为 7+6+5+4+3+2=27,最优。
- 询问 (l,u)=(5,9):选 r=5 时共跑 5 段,收益为 9+8+7+6+5=35;选 r=6 时共跑 14 段,收益同样为 35。取较小的 r=5。
因此第一组数据输出 3 4 5。
样例 2
输入
1
5
2 3 1 4 2
4
1 5
2 3
3 1
4 2
输出
2 2 3 4
说明
共有 5 条跑道,a=[2,3,1,4,2],前缀和 P=[0,2,5,6,10,12]。
- 询问 (1,5):收益在 S=5 与 S=6 处并列最大,对应的最小下标为 r=2(S=5)。
- 询问 (2,3):S=3(r=2)与 S=4(r=3)收益并列最大,取 r=2。
- 询问 (3,1):l=3,u=1,最优为 r=3。
- 询问 (4,2):l=4,u=2,最优为 r=4。
因此输出 2 2 3 4。
数据范围与约定
对全部测试点:1≤t≤104,1≤n≤105,1≤q≤105,∑n≤2×105,∑q≤2×105,1≤ai≤104,1≤l≤n,1≤u≤109。
| 子任务 |
分值 |
约束 |
| 1 |
30 |
n,q≤2×103 |
| 2 |
70 |
无额外限制 |