离散化的性质:
数组的值域跨度很大 但是它非常的稀疏
没有使用二分,直接用哈希表实现
n,m = map(int,input().split())
add = [] # 记录所有增加操作
query = [] # 记录所有查询操作
IndexLst = [] # 记录增加操作和查询操作一共用到的位置索引
# why 30000? add最多对应10000个位置 query最多对应20000个位置 相加一共是30000个位置
for i in range(n):
x,c = map(int,input().split())
add.append([x,c])
IndexLst.append(x)
for i in range(m):
l,r = map(int,input().split())
query.append([l,r])
IndexLst.append(l)
IndexLst.append(r)
# 离散化 先排序 后去重
IndexLst.sort()
IndexLst = list(set(IndexLst))
dict = {}
for idx,i in enumerate(IndexLst):
dict[i] = idx+1 # 将离散化后的下标隐射到1~n方便求取前缀和
a = [0 for i in range(len(IndexLst)+1)] # 记录离散化后压缩了的数组
s = [0 for i in range(len(IndexLst)+1)] # 前缀和数组
# 增加
for x,c in add:
a[dict[x]]+=c # 用离散化的下标在压缩后的数组上增加
# 求前缀和
for i in range(1,len(IndexLst)+1):
s[i] = s[i-1] + a[i]
# 处理询问
for l,r in query:
print(s[dict[r]]-s[dict[l]-1])