AcWing 802. 区间和(注意避坑)
原题链接
简单
作者:
Jacky.C
,
2021-01-16 21:26:45
,
所有人可见
,
阅读 357
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int x,c,l,r;
const int N = 300010; // 因为涉及离散化的变量有3个(x,l,r),所以离散化后的数组大小为3倍的最大值
int a[N];
vector<int> nums; // nums是全体待离散化的数
vector<pair<int,int>> v,q;
int find(int num)
{
int mid, l = 0, r = nums.size()-1;
while(l<r){
mid = l+r>>1;
if(nums[mid] >= num) r = mid;
else l = mid + 1;
}
return l+1;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i = 0; i<n; i++){
cin>>x>>c;
nums.push_back(x);
v.push_back({x,c});
}
for(int j = 0; j<m; j++){
cin>>l>>r;
nums.push_back(l);
nums.push_back(r);
q.push_back({l,r});
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
// 对x离散化,并在数轴上加c
for(int i = 0; i<n; i++){
a[find(v[i].first)] += v[i].second;
}
// 求前缀和,可以直接在a上操作。
// 注意这里循环的长度为nums数组的长度,而非n,这是因为nums里面并不全是来自x的数,还有来自查询l,r的数。所以x离散化后是有可能大于n的。
for(int i=1; i<=nums.size(); i++){
a[i] += a[i-1];
}
// 区间查询
for(int i = 0; i<m; i++){
cout<<a[find(q[i].second)]-a[find(q[i].first)-1]<<endl;
}
return 0;
}