使用lower_bound和upper_bound二分+前缀和处理

#define judge
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int n, m;
const int maxn = 1e5 + 10;
vector<PII> all;
int s[maxn];
int find1(int x) {
  //查找大于等于x的最小的数字
  int l = 0, r = n - 1;
  while (l < r) {
    int m = l + r >> 1;
    if (all[m].first >= x) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  return l;
}
int find2(int x) {
  //查找小于等于x的最大的数字
  int l = 0, r = n - 1;
  while (l < r) {
    int m = l + r + 1 >> 1;
    if (all[m].first <= x) {
      l = m;
    } else {
      r = m - 1;
    }
  }
  return l;
}
int main() {
#ifndef judge
  freopen("E:/yxc/in.txt", "r", stdin);
  freopen("E:/yxc/out.txt", "w", stdout);
#endif
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int pos, val;
    scanf("%d%d", &pos, &val);
    all.push_back(make_pair(pos, val));
  }
  sort(all.begin(), all.end());
  for (int i = 0; i < all.size(); i++) s[i] = all[i].second;
  for (int i = 1; i < n; i++) s[i] += s[i - 1];
  // for (int i = 0; i < n; i++) printf("%d ", s[i]);
  // printf("pos:%d val:%d\n", all[i].first, all[i].second);

  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    int li, ri;
    li = find1(l);
    ri = find2(r);
    // printf("li:%d, ri:%d\n", li, ri);
    if (li == ri && !(all[li].first >= l && all[li].first <= r)) {
      printf("0\n");
    } else {
      int res = s[ri] - s[li - 1];
      printf("%d\n", res);
    }
  }

  return 0;
}