QOJ 14436
给出一个非负整数序列 a_1, a_2, \dots, a_na1,a2,…,an。初始时,你可以创造一个机器人,高度为 [0, d][0,d] 之间的正整数。每当经过一个检查点 a_iai 时,如果当前的高度 hh 满足 h \geq a_ih≥ai,则高度 h \gets h - a_ih←h−ai;否则不会发生任何事。
有 QQ 次询问,每次询问给出两个正整数 l, rl,r (1 \leq l \leq r \leq n1≤l≤r≤n),你需要选择机器人的初始高度,使得依次经过检查点 a_l, \dots, a_ral,…,ar 之后机器人剩下的高度最大,你只需要求出该高度即可。
数据范围:1 \leq n, Q \leq 3 \times 10^51≤n,Q≤3×105,1 \leq d \leq 10^91≤d≤109,0 \leq a_i \leq 10^90≤ai≤109,1 \leq l \leq r \leq n1≤l≤r≤n。
时空限制:11s / 256256MiB。