树状数组+扫描线10pts求条

#include <bits/stdc++.h>

using namespace std;

namespace zcq_qwq {
	const int N = 5e6 + 5;
	
	struct node {
		int x, y, id, type;
	} a[N];
	
	int b[N], c[N], tree[N], ans[N];
	
	int n, m, cnt, tot1, tot2;
	
	int lowbit(int x) {
		return x & -x;
	}
	
	void add(int x, int y) {
		for (int i = x; i <= n; i += lowbit(i)) {
			tree[x] += y;
		}
	}
	
	int ask(int x) {
		int ans = 0;
		for (int i = x; i > 0; i -= lowbit(i)) {
			ans += tree[i];
		}
		return ans;
	}
	
	void main() {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			int x, y;
			cin >> x >> y;
			a[++cnt] = {x, y, 0, 0};
			b[++tot1] = x, c[++tot2] = y; 
		}
		for (int i = 1; i <= m; i++) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			a[++cnt] = {x2, y2, i, 1};
			b[++tot1] = x2, c[++tot2] = y2;
			a[++cnt] = {x1 - 1, y2, i, 2};
			b[++tot1] = x1 - 1, c[++tot2] = y2;
			a[++cnt] = {x2, y1 - 1, i, 2};
			b[++tot1] = x2, c[++tot2] = y1 - 1;
			a[++cnt] = {x1 - 1, y1 - 1, i, 1};
			b[++tot1] = x1 - 1, c[++tot2] = y1 - 1;
		} 
		stable_sort(b + 1, b + tot1 + 1);
		stable_sort(c + 1, c + tot2 + 1);
		tot1 = unique(b + 1, b + tot1 + 1) - b - 1;
		tot2 = unique(c + 1, c + tot2 + 1) - c - 1;
		for (int i = 1; i <= cnt; i++) {
			a[i].x = lower_bound(b + 1, b + tot1 + 1, a[i].x) - b;
			a[i].y = lower_bound(c + 1, c + tot2 + 1, a[i].y) - c;
		}
		stable_sort(a + 1, a + cnt + 1, [](node x, node y) {
			if (x.x != y.x) return x.x < y.x;
			else return x.y < y.y;
		});
		for (int i = 1; i <= cnt; i++) {
			int x = a[i].x, y = a[i].y;
			if (!a[i].id) {
				add(y, 1);
			} else {
				int tmp = ask(y);
				if (a[i].type == 1) {
					ans[a[i].id] += tmp;
				} else {
					ans[a[i].id] -= tmp;
				}
			}
		}
		for (int i = 1; i <= m; i++) {
			cout << ans[i] << endl;
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	zcq_qwq::main();
	return 0;
}