程序说明
alls 用于储存增加和查询的所有数轴上的点, sum 用于保存前缀和结果,
add 保存需要添加的操作,包括数轴位置和值,query 保存询问的左右边界
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
int find (const vector<int>& alls, const 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 l + 1;
}
int main ()
{
// 读入n和m
int n, m;
scanf ("%d%d", &n, &m);
vector<int> sum(n + 2 * m + 1, 0), alls;
vector<PII> add, query;
// 读入数据
for (int i = 0; i < n; i++)
{
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//排序并去重
sort (alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 预处理,将alls的数据映射到1 — n + 2*m
for (int i = 0; i < add.size(); i++)
{
int idx = find(alls, add[i].first);
sum[idx] += add[i].second;
}
// 求前缀和
for (int i = 1; i < sum.size(); i++)
sum[i] += sum[i-1];
// 查询
for (int i = 0; i < query.size(); i++)
{
int l = find(alls, query[i].first);
int r = find(alls, query[i].second);
printf ("%d\n", sum[r] - sum[l - 1]);
}
return 0;
}