AcWing 802. 区间和
这道题对于离散化讲解的非常好
这里离散化的是数组的下标,对于很大的数组下标进行离散化
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 300010;
int n, m;
int a[N], s[N];//a为映射后的数组地址下标是被映射的对象,s是映射后的前缀和数组
typedef pair<int, int> PII;
vector<int> alls;//存所有可能的操作地址,隐形参数是处理过后的地址的地址下标+1为映射的地址
vector<PII> add , query;//添加的操作和查询的操作
int find(int x){
int l=0, r=alls.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ){
int x, y;
cin >> x >> y;
add.push_back({x , y});
alls.push_back(x);
}
for(int i = 0; i < m; i ++ ){
int x, y;
cin >> x >> y ;
query.push_back({x , y});
alls.push_back(x) , alls.push_back(y);//将可能的地址添加到地址下标数组中
}
sort(alls.begin() , alls.end());
alls.erase(unique(alls.begin() , alls.end()) , alls.end());//去重的目的是为了分离出所有可能的操作地址
for(auto item : add){
int x = find(item.first);
a[x] += item.second;
}
for(int i = 1; i < alls.size() + 1; i++) s[i] = s[i - 1] + a[i];
for(auto item : query){
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}