AcWing 802. 区间和
原题链接
简单
作者:
Jasonaowu
,
2024-11-30 10:22:46
,
所有人可见
,
阅读 1
# 查找 x 在离散化后数组中的位置
def find(x, arr):
l, r = 0, len(arr) # [ ) 左闭右开
while l < r:
mid = int((l + r) / 2)
if arr[mid] < x:
l = mid + 1
else:
r = mid
return l + 1
# if __name__=="__main__":
n,m = map(int,input().split())
add = []
alls = [] # 需要离散化的数组
query = []
N = 300010
a = [0] * N
s = [0] * N
for i in range(n): # 读入 +c 操作
x, c = map(int,input().split())
add.append((x, c))
alls.append(x)
for i in range(m):
l, r = map(int,input().split())
query.append((l, r))
alls.append(l)
alls.append(r)
alls = sorted(set(alls))
for pos, c in add:
idx = find(pos, alls) # 查找 x 在 alls 中的下标
a[idx] += c
for i in range(1, len(alls)+1):
s[i] = s[i-1] + a[i]
for l, r in query:
l2 = find(l, alls)
r2 = find(r, alls)
res = s[r2] - s[l2 - 1]
print(res)