离散化

当一个数组的坐标范围特别大的时候，我们可以用离散化来缩小。

数组去重

vector<int> alls;
sort(alls.begin(), alls.end());
  alls.erase(unique(alls.begin(), alls.end()), alls.end());

定义查找函数

这里使用 r+1 我们用坐标 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;
}

AcWing 802：区间和

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 300010;
 
int a[N], s[N];
 
int n, m;
 
vector<int> alls;
 
vector<PII> add, query;
 
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;
}
 
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int x, c;
    scanf("%d%d", &x, &c);
    add.push_back({x, c});
    alls.push_back(x);
  }
  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &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);
    int c = item.second;
 
    a[x] += c;
  }
 
  // 计算前缀和
  for (int i = 1; i <= alls.size(); i++) {
    s[i] = s[i - 1] + a[i];
  }
 
  // 处理所有查询 query
  for (auto item : query) {
    int l = find(item.first);
    int r = find(item.second);
    cout << s[r] - s[l - 1] << endl;
  }
 
  return 0;
}