AcWing 802. 区间和-哈希表实现,效率慢了一些,但是够用
原题链接
简单
作者:
Buctpeng
,
2024-03-04 21:00:06
,
所有人可见
,
阅读 21
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int N = 5e5+10;
int n,m;
int a[N],c[N];
pair<int,int> b[N];
set<int> s;
map<int,int> h;
int sum[N];
int p[N];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;++i){
cin>>a[i]>>c[i];
s.insert(a[i]);
}
for(int i=0;i<m;++i){
cin>>b[i].first>>b[i].second;
s.insert(b[i].first);
s.insert(b[i].second);
}
int cnt = 1;
for(auto t:s){
h[t] = cnt++;
}
for(int i=0;i<n;++i){
int x = a[i],y = c[i];
int k = h[x];
p[k]+=y;
}
for(int i=1;i<=s.size();++i){
sum[i] = sum[i-1]+p[i];
}
for(int i=0;i<m;++i){
int l = b[i].first, r = b[i].second;
l = h[l],r = h[r];
cout<<sum[r] - sum[l-1]<<"\n";
}
}