AcWing 802. 区间和
原题链接
简单
作者:
Ron.W
,
2021-08-17 07:13:06
,
所有人可见
,
阅读 227
import sys
def solve(L):
n = int(L[0].split(' ')[0])
to_add = [ list(map(int, line.split(' '))) for line in L[1:n+1] ]
to_query = [ list(map(int, line.split(' '))) for line in L[n+1:] ]
coord = [x for sub in to_query for x in sub] + [x for x, c in to_add]
coord.sort()
coord = list(set(coord))
def find(x):
l,r = 0, len(coord)-1
while l<r:
m = (r-l) // 2 + l
if coord[m] >= x:
r = m
else:
l = m + 1
return r + 1
S = [0] * len(coord) + [0]
coord_value = [0]*len(coord) + [0]
for x,c in to_add:
coord_value[find(x)] += c
for i in range(1, len(coord)+1):
S[i] = S[i-1] + coord_value[i]
for l,r in to_query:
print(S[find(r)] - S[find(l)-1])
solve(list(sys.stdin))