时间复杂度

离散化：$O(n)$
累加：$O(n\log n)$
前缀和：$O(n)$
查询：$O(m\log n)$

#include <bits/stdc++.h>

using namespace std;
const int MAX = 1e5 + 10;
int a[MAX], b[MAX];
vector<int> xs; // 存储离散化值

// 二分查最后一个<=x的坐标
int findx(int x) {
  if (xs.size() == 0 || x < xs[0])
    return -1;
  if (x > xs[xs.size() - 1])
    return xs.size() - 1;

  // 循环不变式: [L, l] < x, [r, R] > x
  int l = -1, r = xs.size();
  while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (xs[m] == x)
      return m;
    if (xs[m] < x)
      l = m;
    if (xs[m] > x)
      r = m;
  }
  return l;
}

int main() {
  int n, m;
  cin >> n >> m;

  // 输入
  int x, c;
  vector<array<int, 2>> ins;
  for (int i = 0; i < n; ++i) {
    cin >> x >> c;
    xs.push_back(x);
    ins.push_back({x, c});
  }

  // 离散化
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());

  // 累加
  int j = 0;
  for (int i = 0; i < n; ++i) {
    x = ins[i][0];
    c = ins[i][1];
    j = findx(x) + 1;
    a[j] += c;
  }

  // 前缀和
  for (int i = 1; i <= n; ++i) {
    b[i] = b[i - 1] + a[i];
  }

  // 查询
  int l, r;
  while (m--) {
    cin >> l >> r;
    cout << b[findx(r) + 1] - b[findx(l - 1) + 1] << endl;
  }

  return 0;
}