AcWing 802. 区间和-python
原题链接
简单
作者:
Actor丶
,
2020-03-14 09:40:25
,
所有人可见
,
阅读 1646
def find(x):
"""二分查找模板,从索引数组alls中找到大于等于x的最小的索引"""
l = 0
r = len(alls)-1
while l<r:
mid = l+r>>1
if alls[mid]>=x: r = mid
else: l = mid+1
return l+1
if __name__=="__main__":
n, m = map(int, input().split())
N = 300010
a = [0]*N
s = [0]*N
add = []
query = []
alls = []
for i in range(n):
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 = list(set(sorted(alls)))
for x, c in add:
x2 = find(x)
a[x2]+=c
for i in range(1, len(alls)+1):
s[i] = s[i-1]+a[i]
for l, r in query:
l2 = find(l)
r2 = find(r)
res = s[r2]-s[l2-1]
print(res)
排序那一步里,set返回的是无需数组,排序不是白做了吗
有道理,应该最后排序
可以用bisect 稍微简化代码
不愧是用c++写出来的python真像