【题目来源】
AcWing：802. 区间和 - AcWing题库
【题目描述】
假定有一个无限长的数轴，数轴上每个坐标上的数都是 \(0\)。
现在，我们首先进行 \(n\) 次操作，每次操作将某一位置 \(x\) 上的数加 \(c\)。
接下来，进行 \(m\) 次询问，每个询问包含两个整数 \(l\) 和 \(r\)，你需要求出在区间 \([l,r]\) 之间的所有数的和。
【输入】
第一行包含两个整数 \(n\) 和 \(m\)。
接下来 \(n\) 行，每行包含两个整数 \(x\) 和 \(c\)。
再接下来 \(m\) 行，每行包含两个整数 \(l\) 和 \(r\)。
【输出】
共 \(m\) 行，每行输出一个询问中所求的区间内数字和。
【输入样例】
3 3
1 2
3 6
7 5
1 3
4 6
7 8
【输出样例】
8
0
5
【解题思路】
【算法标签】
《AcWing 802 区间和》 #离散化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII; // 定义pair类型，存储两个整数
const int N = 300010; // 定义最大可能的数据范围int n, m; // n: 插入操作数, m: 查询操作数
int a[N], s[N]; // a: 离散化后的数组, s: 前缀和数组
vector<int> alls; // 存储所有需要离散化的坐标
vector<PII> add, query; // add: 存储插入操作, query: 存储查询操作/*** 二分查找函数，找到x在alls中的位置（离散化后的值）* @param x 需要查找的值* @return 离散化后的索引（从1开始）*/
int find(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 r + 1; // 返回离散化后的索引（从1开始）
}int main()
{// 输入插入操作数和查询操作数cin >> n >> m;// 处理插入操作for (int i = 0; i < n; i++){int x, c;cin >> x >> c;add.push_back({x, c}); // 存储插入操作alls.push_back(x); // 存储需要离散化的坐标}// 处理查询操作for (int i = 0; i < m; i++){int l, r;cin >> 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());// 处理插入操作（离散化后）for (auto item : add){int x = find(item.first); // 获取离散化后的坐标a[x] += item.second; // 在对应位置累加值}// 预处理前缀和数组for (int i = 1; i <= alls.size(); i++){s[i] = s[i - 1] + a[i];}// 处理查询操作for (auto item : query){int l = find(item.first); // 获取离散化后的左边界int r = find(item.second); // 获取离散化后的右边界cout << s[r] - s[l - 1] << endl; // 输出区间和}return 0;
}
【运行结果】
3 3
1 2
3 6
7 5
1 3
4 6
7 8
8
0
5