AcWing 802. 离散化
原题链接
简单
区间和
输入样例
3 3 //操作次数 查询次数
1 2 //将某一位置x上的数加c
3 6
7 5
1 3 //在区间[l, r]之间的所有数的和
4 6
7 8
输出样例
8
0
5
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=4e5+10;
vector<int> v;
int x[N], c[N];//插入坐标 插入的值
int l[N], r[N];//左端点 右端点
LL sum[N];//前缀和
int find(int x)//查找坐标
{
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &x[i], &c[i]);
v.push_back(x[i]);
}
for (int i = 0; i < m; i++)
{
scanf("%d%d", &l[i], &r[i]);
v.push_back(l[i]);
v.push_back(r[i]);
}
sort(v.begin(), v.end());//坐标从小到大排序
v.erase(unique(v.begin(), v.end()), v.end());//对坐标去重,并删去重复的坐标
for (int i = 0; i < n; i++)
sum[find(x[i])] += c[i];//记录插入的数值
n = v.size();//更新总长度
for (int i = 1; i < n; i++)
sum[i] += sum[i - 1];//前缀和
for (int i = 0; i < m; i++)
printf("%lld\n", sum[find(r[i])] - sum[find(l[i]) - 1]);
return 0;
}