题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
近下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
算法1
离散化
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;//l + r + n;
vector<int> als;
vector<PII> add, query;
int a[N];
int find(int x)//二分;
{
int l = 0, r = als.size() - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (als[mid] <= x) l = mid;
else r = mid - 1;
}
return l + 1;
}
int main()
{
int n, m;
cin >> n >> m;
while (n --)
{
int x, c;
scanf("%d%d", &x, &c);
als.push_back(x);
add.push_back({x, c});
}
while(m --)
{
int l, r;
scanf("%d%d", &l, &r);
als.push_back(l);
als.push_back(r);
query.push_back({l, r});
}
sort(als.begin(), als.end());
als.erase(unique(als.begin(), als.end()), als.end());//去重;
//处理增加;
for (auto item : add)
{
int x = find(item.first);
a[x] += item.second;
}
//求前缀和;
for (int i = 1; i <= als.size(); i ++)
a[i] += a[i - 1];
//处理询问,通过前缀和;
for (auto item : query)
{
int x = find(item.first);
int y = find(item.second);
printf("%d\n", a[y] - a[x - 1]);
}
return 0;
}