AcWing 802. 区间和
原题链接
简单
作者:
minux
,
2020-04-22 10:49:32
,
所有人可见
,
阅读 490
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=3e5+5; // 设计离散化后的区间大小(操作数(插入位置, 查询左端点, 查询右端点) X 区间大小)
int n, m;
int a[N], b[N];
vector<int> ALL; // 离散化数组
vector<PII> ADD; // 存储值增加操作
vector<PII> QUERY; // 存储查询操作
// 找到大于等于x的最小值的位置(下标从1开始, for 前缀和)
int find(int x){
int l=0; int r=ALL.size()-1;
while(l<r){
int mid = l+(r-l)/2;
if(ALL[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;
}
int main(){
cin>>n>>m;
memset(a, 0x00, sizeof a);
memset(b, 0x00, sizeof b);
// 读取n组值增加操作
for(int i=0; i<n; ++i){
int x, c;
cin>>x>>c;
ADD.push_back({x, c});
ALL.push_back(x);
}
// 读取m组查询操作
for(int i=0; i<m; ++i){
int l, r;
cin>>l>>r;
QUERY.push_back({l, r});
ALL.push_back(l);
ALL.push_back(r);
}
// 去重(构成单调数组, for 二分查询(find(x)))
sort(ALL.begin(), ALL.end());
ALL.erase(unique(ALL.begin(), ALL.end()), ALL.end());
// ADD
for(auto &add: ADD){
int pos = find(add.first);
a[pos]+=add.second;
}
// 前缀和数组
for(int i=1; i<=ALL.size(); ++i){
b[i]=b[i-1]+a[i];
}
// QUERY
for(auto &query: QUERY){
int lpos = find(query.first);
int rpos = find(query.second);
cout<<b[rpos]-b[lpos-1]<<endl;
}
return 0;
}