#include using namespace std; typedef pair PII; const int N = 300010; // 上限,n+2*m+10 int a[N]; // 映射后的数组 int s[N]; // a数组的前缀和数组 vector alls; // 坐标集合 vector add; // 1、哪个位置,2:加上多少 vector query; // 1、开始点,2:结束点 int n, m; /** * 功能:利用二分法查找原索引x的映射后索引值 * 核心思路:原来是第几个是不变的,离散化后还是第几个,建立起了映射关系。 * @param x 原来的索引号 * @return 映射后小数组内的索引号 */ 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 l; } // 883 ms int main() { // 输入数据 cin >> n >> m; // 录入原始数据 while (n--) { int x, c; cin >> x >> c; // 记录位置与值 add.push_back({x, c}); // 将位置记录到alls里 alls.push_back(x); } // 读入查询范围 int l, r; while (m--) { 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()); // 生成a数组,每次都在映射后的坐标位置将值变大c for (int i = 0; i < add.size(); i++) { PII item = add[i]; // find返回的是下标从0开始的位置,这里为了使用前缀和,要求a数据下标从1开始,有1个偏移量 int x = find(item.first) + 1; // 映射为小范围的索引值 a[x] += item.second; } // 预处理前缀和 for (int i = 1; i < N; i++) s[i] = s[i - 1] + a[i]; // 处理询问(前缀和应用) for (int i = 0; i < query.size(); i++) { PII item = query[i]; // 根据原来的位置值,计算出映射后的位置值 l = find(item.first) + 1; r = find(item.second) + 1; // 利用一维前缀和计算区间和 cout << s[r] - s[l - 1] << endl; } return 0; }