二分 - 坐标放大2倍以防止小数点 - 二分, 找到 在 $[L, R]$ 内, 即 $[2 \times L, 2 \times R]$ 内, 的线段中点坐标 $l + \frac{r-l}{2} $ 即 $2l + r - l = l + r$ (注意, l, r 是坐标) - 使用二分找到 最后一个大于等于 $2R$ 的点的索引 减去 第一个大于等于 $2L$ 的点的索引 - (不要忘记排序点) - 二分找到 最后一个大于等于 $2R$ 的点的索引等价于二分早点第一个大于等于 $2R + 1$ 的点的左边那个索引 (即lower_bound(2R + 1) - 1 )(这也是为什么下面不用 + 1 (因为和 - 1抵消了)) (devc++坏掉了, 输入中文会乱码, 下面代码可能有点lj英语+工地日语的注释)😕 ```C++ #include <cstdio> #include <vector> #include <algorithm> using namespace std; // 查找第一个>=t的元素的索引, 没有则返回arr.size() int lower_bound(const vector<int>& arr, int t) { // find one >= t no num int l = 0, r = arr.size() - 1; while (l <= r) { int mid = l + ((r - l) >> 1); if (arr[mid] < t) { l = mid + 1; } else { r = mid - 1; } } return l; } int main() { int n, m; scanf("%d %d", &n, &m); vector<int> arr(n); for (int i = 0, l, r; i < n; ++i) { scanf("%d %d", &l, &r); arr[i] = l + r; // zhong dian } sort(arr.begin(), arr.end()); for (int i = 0, L, R; i < m; ++i) { scanf("%d %d", &L, &R); // er-fen find: one >= L // AND ond <= R printf("%d\n", lower_bound(arr, R * 2 + 1) - lower_bound(arr, L * 2)); // 抵消 减一 } return 0; } ``` 前缀和 (数组大小我乱开的...能过的...) ```cpp #include <cstdio> #include <vector> #include <array> #include <algorithm> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); array<int, 100001 * 20> arr; array<int, 100001 * 20 +1> sumArr; for (int i = 0, l, r; i < n; ++i) { scanf("%d %d", &l, &r); ++arr[l + r]; } for (int i = 0; i < 100001 * 20; ++i) { sumArr[i + 1] = arr[i] + sumArr[i]; } for (int i = 0, L, R; i < m; ++i) { scanf("%d %d", &L, &R); printf("%d\n", sumArr[2 * R + 1] - sumArr[2 * L]); } return 0; } ```

``` #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 0x3f3f3f3f3f3f3f3f; const int N = 1e7 + 10; int n, m; int arr[N]; signed main(){ cin >> n >> m; for(int i = 0; i < n; ++i){ int a, b; cin >> a >> b; arr[(a + b)]++; } for(int i = 1; i <= 2000010; ++i) arr[i] += arr[i-1]; for(int i = 0; i < m; ++i){ int a, b; cin >> a >> b; a *= 2; b *= 2; cout << arr[b] - arr[a - 1] << endl; } return 0; } ```