如上所述,当查询次数不多(q 不大)时,上面的方法完全没问题。但是如果 p 和 q 都非常大,上面的方法就存在超时的风险。所以,当查询次数很多时,通常我们会先创建查询数组。以题目为例,由一条有 n 个坐标点的 “街道”,我们可以创建一个长度为 n 的数组。然后根据每个 “路灯” 的亮度,找出每个坐标点的最大 “亮度”。这样当后面查询的时候,只要从这个数组里取出相应的答案即可。
n, m = map(int, input().split())
h = [[0, n]] # 初始化栈,所有池塘都干涸的情况
for _ in range(m):
v = int(input())
if v >= 0: # 水位上升
temp = v
while h and h[-1][1] < temp:
temp -= h.pop()[1]
if not h: h.append([n, 0]) # 所有池塘都满了
else:
h[-1][1] -= temp # 更新栈顶 “水面宽度”
for i in h: i[0] += v # 更新栈内所有 “平行四边形” 的 “高度”
else:
# 请参考题解试着自己补全水位下降的代码
s = h[0][0]*(1+h[0][0])//2 + sum(i[0]*i[1] for i in h)
print(s)