AcWing 802. 区间和
原题链接
简单
作者:
贝多芬
,
2022-02-13 13:24:52
,
所有人可见
,
阅读 137
python超时
n,m = map(int,input().split())
d = {}
for _ in range(n):#读进数据
x,c = map(int,input().split())
if x in d:
d[x] += c
else:
d[x] = c
query = []
for _ in range(m):#保存查询
l,r = map(int,input().split())
query.append((l,r))
if l not in d:
d[l] = 0
if r not in d:
d[r] = 0
d_k = sorted(d)
d[d_k[0] - 1] = 0
tmp = d_k[0] - 1
for x in d_k:#数据改为前缀和数据
d[x] = d[tmp] + d[x]
tmp = x
d_k = [d_k[0] - 1] + d_k
for x in query:#每次查询
print(d[x[1]]-d[d_k[d_k.index(x[0])-1]])#找到当前查询边界的左边界的前一个数,可能超时原因
是的呢