题目：
假定有一个无限长的数轴，数轴上每个坐标上的数都是 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
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
时/空限制：2s / 64MB
题目分析：
思路：
第一想法是直接给每个位置操作完之后，求一个前缀和，然后查询区间直接算前缀和就好了。但是发现操作的数据范围是 − 1 0 9 ≤ l ≤ r ≤ 1 0 9 −10^9≤l≤r≤10^9 −109≤l≤r≤109，显然开不了那么大的数组，但是看其他数据范围，发现 n , m n,m n,m的大小为 1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105，也就是说我们只会用到 1 0 5 10^5 105个点，虽然这些点离散的分布在 [ 1 , 1 0 9 ] [1, 10^9] [1,109]之间，但是我们可以通过将这些点分别映射到一个数组中去，比如，如图：
我们保证存入arr中的这些位置为升序。
所以我们就可以通过二分查找的方式，在 a r r arr arr中快速找到所需要操作的位置在arr中的哪个位置(因为arr中存储的坐标是升序排列的)，找到所对应的位置之后，我们就可以在val数组中对该位置进行加数的操作，这样我们就实现了对 [ 1 , 1 0 9 ] [1, 10^9] [1,109]这些数的离散化。
代码如下：
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define PII pair<int, int>using namespace std;
const int maxn = 3e5 + 10;int n, m;int a[maxn], s[maxn]; // 一个记录需要离散之后的数， 一个求前缀和
vector<PII> adds, qs; // 添加操作，查询操作的一对数
vector<int> alls; // 存储去重后的值 int find(int x){ // 找到alls中第一个大于等于x的位置 映射到a中 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(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 0; i < n; i ++ ){int x, c;cin >> x >> c;alls.push_back(x);adds.push_back({x, c});}for(int i = 0; i < m; i++ ) {int l, r;cin >> l >> r;qs.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());for(int i = 0; i < adds.size(); i ++ ){ // 处理加值 int x = find(adds[i].first); // 离散化 a[x] += adds[i].second; // 给离散化之后的坐标加值 }for(int i = 1; i <= alls.size(); i ++ ){ // 求a的前缀和，为了求区间和 s[i] = s[i - 1] + a[i];}for(const auto &it : qs){int xa = find(it.first), xb = find(it.second);cout << s[xb] - s[xa - 1] << endl;}return 0;
}
第二种方法：明日更。
