AcWing 802. 区间和-Python
原题链接
简单
作者:
生日快乐
,
2021-02-12 19:02:09
,
所有人可见
,
阅读 257
思路和y总的完全一致,只是用py实现了下,大家可以参考下,因为我也是初学,有误之处还请大家指出。
n,m=map(int,input().split())
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)
def find(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 r+1
alls=list(set(alls))
alls.sort()
a=[0]*(len(alls)+100)
s=[0]*(len(alls)+100)
for i in add:
x=find(i[0])
a[x]+=i[1]
for i in range(1,len(alls)+1):
s[i]=s[i-1]+a[i]
for i in query:
l=find(i[0]);r=find(i[1])
print(s[r]-s[l-1])