AcWing 802. 区间和
原题链接
简单
作者:
走不到也得走
,
2020-01-17 10:35:43
,
所有人可见
,
阅读 448
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=3e5+10;
int a[N],s[N];
vector<int>all;
vector<PII>add,query;
//vector<PII>::iterator item;
int find(int x)
{
int l=0,r=all.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(all[mid]>=x)r=mid;
else l=mid+1;
}
return r+1;
}
int main()
{
int n,m;
cin>>n>>m;
int x,c;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&c);
add.push_back({x,c});
all.push_back(x);
}
int l,r;
for(int i=0;i<m;i++)
{
scanf("%d%d",&l,&r);
query.push_back({l,r});
all.push_back(l);
all.push_back(r);
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(auto item:add)
{
int x=find(item.first);
a[x]+=item.second;
}
for(int i=1;i<=all.size();i++)
s[i]=s[i-1]+a[i];
for(auto it:query)
{
int l=find(it.first),r=find(it.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}