二分

• 坐标放大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抵消了))

#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;
}

前缀和

#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;
}