求区间和
这道题使用了 二分 + 前缀和 + 离散化的方法
主要思路是 : 使用vector来存储很大的坐标轴上需要改变的坐标点的信息
排序去重后之后将这些很大的坐标点映射到1 - 100010上去,即使用allnums中的下标作为很大的坐标轴上点的坐标的映射
映射完成之后,在对前缀和进行添加时,需要先通过二分法找到坐标点映射的下标,再之后就是正常的前缀和的操作了
有两个需要注意的点
1 : 去重,在allnums中的去重,保证同一个坐标点只能有一个映射
2 : 在求映射关系的时候,需要将映射的下标值 + 1 ,因为下标是从0开始的,而前缀和是从1开始的
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e5 + 10;
typedef pair<int,int>PII;
int a[N],s[N];
vector<PII> add ,query;
vector<int> allnums;
int findx(int x){
int l = 0 , r = allnums.size() - 1;
while(l < r){
int mid = (l + r ) / 2;
if(allnums[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1; // + 1的原因是下标从0开始,但是数字是从1开始,所以从数字到下标的映射需要加上1
}
int main(){
int n,m;
cin >> n >> m;
while(n--){
int x,y;
cin >> x >> y;
add.push_back({x,y});
allnums.push_back(x);
}
while(m--){
int x , y;
cin >> x >> y;
allnums.push_back(x);
allnums.push_back(y);
query.push_back({x,y});
}
sort(allnums.begin(),allnums.end());
allnums.erase(unique(allnums.begin(),allnums.end()),allnums.end());
for(auto iter : add){
int x = findx(iter.first);
a[x] += iter.second;
}
for(int i = 1;i <= allnums.size();++i) s[i] = s[i - 1] + a[i];
for(auto iter : query){
int l = findx(iter.first);
int r = findx(iter.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}