KDT 做法求助

#include <bits/stdc++.h>
 
using namespace std;

typedef array<int, 2> pnt;
 
const int MAXN = 4e5 + 10;

struct node {
	int l, r, w, s; pnt x, tl, tr;
	node(pnt x = {}) : l(0), r(0), w(0), s(0), x(x), tl(x), tr(x) {}
} t[MAXN * 19]; int rt[MAXN], cnt, a[MAXN];

inline 
void pushup(int p) {
	t[p].tl = t[p].tr = t[p].x;
	if (t[p].l) {
		for (int i = 0; i < 2; i++) t[p].tl[i] = min(t[p].tl[i], t[t[p].l].tl[i]);
		for (int i = 0; i < 2; i++) t[p].tr[i] = max(t[p].tr[i], t[t[p].l].tr[i]);
	}
	if (t[p].r) {
		for (int i = 0; i < 2; i++) t[p].tl[i] = min(t[p].tl[i], t[t[p].r].tl[i]);
		for (int i = 0; i < 2; i++) t[p].tr[i] = max(t[p].tr[i], t[t[p].r].tr[i]);
	}
}

int build(int l, int r, int k = 0) {
	if (l > r) return 0; int mid = l + r >> 1;
	nth_element(a + l, a + mid, a + r + 1, [k](int i, int j) { return t[i].x[k] < t[j].x[k]; });
	int p = a[mid]; t[p].l = build(l, mid - 1, k ^ 1), t[p].r = build(mid + 1, r, k ^ 1);
	return pushup(p), p;
}

void add(pnt x, int p) {
	if (!p) return ;
	if (x[0] < t[p].tl[0] || x[0] > t[p].tr[0]) return ;
	if (x[1] < t[p].tl[1] || x[1] > t[p].tr[1]) return ;
	t[p].s++;
	if (x[0] == t[p].x[0] && x[1] == t[p].x[1]) return t[p].w++, void();
	add(x, t[p].l), add(x, t[p].r);
}

int __cnt;

int ask(pnt x, int p) {
	__cnt++;
	if (!p) return 0;
	if (x[0] > t[p].tr[0] || x[1] > t[p].tr[1]) return 0;
	if (x[0] <= t[p].tl[0] && x[1] <= t[p].tl[1]) return t[p].s;
	if (x[0] > t[p].x[0] || x[1] > t[p].x[1]) return ask(x, t[p].l) + ask(x, t[p].r);
	return t[p].w + ask(x, t[p].l) + ask(x, t[p].r);
}

int n, m, b[MAXN];

inline 
void tadd(int k, pnt x) {
	for (int i = k; i <= n; i += i & -i) add(x, rt[i]);
}

inline 
int task(int k, pnt x) {
	int res = 0; __cnt = 0;
	for (int i = k; i; i &= i - 1) res += ask(x, rt[i]);
	assert(__cnt <= 5000); // 就这玩意。n<=2e5 都会 assert 失败。
	return res;
}

struct qnode {
	int a, b, c, d, id;
	qnode(int a = 0, int b = 0, int c = 0, int d = 0, int id = 0) :
		a(a), b(b), c(c), d(d), id(id) {}
	bool operator < (const qnode &rhs) const { return a == rhs.a ? id < rhs.id : a < rhs.a; }
} q[MAXN << 1];

int ans[MAXN], id[MAXN], rk[MAXN];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, a, b, c, d; i <= n; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		::b[i] = b, q[i] = qnode(a, b, c, d, -i);
	}
	for (int i = 1, a, b, c, d; i <= m; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		q[n + i] = qnode(a, b, c, d, i);
	}
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++) id[i] = i;
	sort(id + 1, id + n + 1, [](int i, int j) { return q[i].b < q[j].b; });
	for (int i = 1; i <= n; i++) rk[id[i]] = i;
	for (int i = 1; i <= n; i++) {
		int len = i & -i;
		for (int j = 1; j <= len; j++) {
			int k = id[i - j + 1];
			t[++cnt] = pnt({ q[k].c, q[k].d }), a[j] = cnt;
		}
		rt[i] = build(1, len);
	}
	sort(q + 1, q + n + m + 1);
	for (int i = 1; i <= n + m; i++) {
		if (q[i].id < 0) tadd(rk[-q[i].id], pnt({ q[i].c, q[i].d }));
		else {
			int j = upper_bound(::b + 1, ::b + n + 1, q[i].b) - ::b - 1;
			ans[q[i].id] = task(j, pnt({ q[i].c, q[i].d }));
		}
	}
	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}