题目描述

区间和，模板题，样例很死。

算法

(离散化前导：用字典sorted转二维实现；二分查找；计算加和：前缀和;) $O(m*logn)$

import bisect

dic = {} # global

n,m = map(int,input().split())

for i in range(n):
x,c = map(int,input().split())
if x in dic:
dic[x] += c
else:
dic[x] = c

lst = sorted(dic.items(), key=lambda item: item[0]) # 现在是列表套元组 按第一个排序
keys = [x[0] for x in lst] # 先把二分值拿出来，不要在后面用comprehension，用了复杂度就是mn了！！！

prefix_sum = [0] * (len(lst) + 1)
for i in range(len(lst)):
prefix_sum[i + 1] = prefix_sum[i] + lst[i][1] # 前缀和

ans = []
for i in range(m): # 复杂度O（m logn）
l,r = map(int,input().split())
if r < lst[0][0] or l > lst[-1][0]: ans.append(0); continue
else:
last = bisect.bisect_left(keys, l)
pre = bisect.bisect_right(keys, r)
if last == 0:
ans.append(prefix_sum[pre])
else:
ans.append(prefix_sum[pre] - prefix_sum[last])

[print(i) for i in ans]

参考文献

暂无