离散化
作者:
Oct_9
,
2024-04-07 16:52:44
,
所有人可见
,
阅读 9
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300000 + 10; //数据范围是所有不重复下标的最大可能值,最多有300000个
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
// 所谓离散化,就是对于所有数字做一个一一对应的映射,同时
// 同时把松散的数据范围映射到一个紧凑的范围之中,而产生这种映射的方法的最容易想到的办法就是
// 把数组去重排序然后取下标(或者+1,不影响双射)
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, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++)
{
int l, r;
cin >> l >> r;
query.push_back({l, r});
alls.push_back(r);
}
// 去重
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(); 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;
}
}