这道题题意本身不难，但是由于数组无限长并且元素的数据范围最大到了$10^9$，显然开了不了$10^9$这么大的数组，需要压缩坐标，这个时候就引入了我们的基础算法之一——离散化

离散化可以将数据范围映射到一个较小的离散集合，实现了坐标压缩。大大节省了空间，便于使用数组来保存。

离散化最推荐的模板

ps:unordered_map, map, set都试过了，没有这种写法快，但是都能过，大概需要开销下面的2.5倍开销时间，set常数太大了，最慢，大概开销了3倍的时间
个人用的开区间写法，不清楚的可以看我的开区间模板(点这里)

#define all(_) _.begin(),_.end()//最前面的宏，便于写
vector<int> alls;//保存所有需要离散化处理的值

//离散化
sort(all(alls));
alls.erase(unique(all(alls)), alls.end());

//查找对应离散化后新的下标 
auto find = [&](int x)->int{
  int l = -1, r = alls.size() + 1;
  while (l + 1 != r) {
    int mid = (l + r) / 2;
    if (alls[mid] >= x) r = mid;
    else l = mid;
  }
  return r + 1;//让新下标从1开始，方便理解和后续操作
};

题目思路:

1.离散化$O((n+m)*log(n+m))$
2.二分查找$O(log(n+m))$
3.前缀和$O(n+m)$
4.离线处理$O(m*log(n+m)$

时间复杂度$O((n+m)*log(n+m)$

#include <iostream>
#include <vector>
#include <algorithm>
#define all(_) _.begin(),_.end()
using namespace std;
constexpr int N = 3e5;
typedef pair<int,int> PII;
int n, m;
int a[N+50], s[N+50];//差分数组和前缀和数组
vector<int> alls;//保存所有出现过的坐标，便于后面的离散化
vector<PII> add, query;//保存添加和查询的操作，便于后面离线操作
int main(){
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    int x, c; 
    cin >> x >> c;
    add.push_back({x, c});//保存添加操作
    alls.push_back(x);//保存出现过的坐标
  }

  for(int i = 1; i <= m; ++i) {
    int l, r;
    cin >> l >> r;
    query.push_back({l, r});//保存查询操作
    alls.push_back(l);//保存出现过的坐标
    alls.push_back(r);//保存出现过的坐标
  }
  //排序去重离散化
  sort(all(alls));
  alls.erase(unique(all(alls)), alls.end());//去重是为了减少时间常数，
  //如果重复的特别多就有效(ps:此题去不去都能过）

  //二分找到离散化后对应的新下标
  auto find = [&](int x)->int{
    int l = -1, r = alls.size() + 1;
    while (l + 1 != r) {
      int mid = (l + r) / 2;
      if (alls[mid] >= x) r = mid;
      else l = mid;
    }
    return r + 1;//让新的离散的下标从1开始，方便理解和后续操作
  };

  //离线操作添加
  for(auto [x, c] : add) {
    a[find(x)] += c;
  }
  //更新前缀和数组
  for(int i = 1; i <= (int)alls.size(); ++i) {
    s[i] = s[i-1] + a[i];
  }
  //离线操作查询
  for(auto [l, r] : query) {
    cout << s[find(r)] - s[find(l)-1] << "\n";
  }
  return 0;
}