802. 区间和（离散化）

题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是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

思路：标准的离散化，给的数据和范围很大，但总共也只有n个数，所以可以给这n这数就行重新编号。 代码如下：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e6 + 10; typedef long long ll; typedef pair<int, int> p; int a[N], sum[N]; p arr[N], query[N]; int n ,m; vector<int>alls; //重新编号 int Find(int x) //查找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() { int l ,r ; cin >>n >> m; for(int i = 0; i < n; i++){ cin >> arr[i].first >> arr[i].second; alls.push_back(arr[i].first); } for(int i = 0; i < m; i++){ cin >> l >> r; query[i].first = l; query[i].second = 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 < n; i++){ int x = Find(arr[i].first); a[x] += arr[i].second; } for(int i = 1; i <= alls.size(); i++) sum[i] = sum[i - 1] + a[i]; for(int i = 0; i < m; i++){ int l = Find(query[i].first); int r = Find(query[i].second); cout << sum[r] - sum[l - 1] << endl; } return 0; }