萌新初学KDT，一直 MLE，别骂求帮助

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
void Min(int &x, int y) { if(x > y) x = y; }
void Max(int &x, int y) { if(x < y) x = y; }
const int N = 2e5 + 7;
int n, op, lastans, f[N], tot, rt, X[N], Y[N], val[N], sum[N], L[N], R[N], U[N], D[N], siz[N], d[N], ch[N][2];
db arpha = 0.7;
bool bad(int x) {
	return (db) max(siz[ch[x][0]], siz[ch[x][1]]) >= arpha * siz[x];
}
void print(int id) {
	if(ch[id][0]) print(ch[id][0]);
	f[++tot] = id;
	if(ch[id][1]) print(ch[id][1]);
}
void upd(int id) {
	siz[id] = siz[ch[id][0]] + siz[ch[id][1]] + 1, sum[id] = sum[ch[id][0]] + sum[ch[id][1]] + val[id];
	L[id] = R[id] = X[id], U[id] = D[id] = Y[id];
	if(ch[id][0]) Min(L[id], L[ch[id][0]]), Max(R[id], R[ch[id][0]]), Min(D[id], D[ch[id][0]]), Max(U[id], U[ch[id][0]]);
	if(ch[id][1]) Min(L[id], L[ch[id][1]]), Max(R[id], R[ch[id][1]]), Min(D[id], D[ch[id][1]]), Max(U[id], U[ch[id][1]]);
}
int build(int l, int r) {
	if(l > r) return 0;
	int mid = (l + r) >> 1;
	db av1 = 0, av2 = 0, val1 = 0, val2 = 0;
	L(i, l, r) av1 += X[i], av2 += Y[i];
	av1 /= (r - l + 1), av2 /= (r - l + 1);
	L(i, l, r) val1 += (av1 - X[i]) * (av1 - X[i]), val2 += (av2 - Y[i]) * (av2 - Y[i]);
	if(val1 > val2) nth_element(f + l, f + mid, f + r + 1, [&](int x, int y) { return X[x] < X[y]; }), d[f[mid]] = 1;
	else nth_element(f + l, f + mid, f + r + 1, [&](int x, int y) { return Y[x] < Y[y]; }), d[f[mid]] = 2;
	ch[f[mid]][0] = build(l, mid - 1);
	ch[f[mid]][1] = build(mid + 1, r);
	upd(f[mid]);
	return f[mid];
}
void rebuild(int &id) {
	tot = 0, print(id), id = build(1, tot);
}
void ins(int &id, int x) {
	if(!id) {
		id = x, d[x] = 1, upd(x);
		return;
	}
	if(d[id] == 1) {
		if(X[x] <= X[id]) ins(ch[id][0], x);
		else ins(ch[id][1], x);
	}
	else {
		if(Y[x] <= Y[id]) ins(ch[id][0], x);
		else ins(ch[id][1], x);
	}
	upd(id);
	if(bad(id)) rebuild(id);
}
int query(int id, int l, int r, int d, int u) {
	if(!id || l > R[id] || r < L[id] || d > U[id] || u < D[id]) return 0;
	if(l <= L[id] && R[id] <= r && d <= D[id] && U[id] <= u) return sum[id];
	int res = 0;
	if(l <= X[id] && X[id] <= r && d <= Y[id] && Y[id] <= u) res = val[id];
	return query(ch[id][0], l, r, d, u) + query(ch[id][1], l, r, d, u) + res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	while(1) {
		cin >> op;
		if(op == 1) {
			++tot, cin >> X[tot] >> Y[tot] >> val[tot];
			X[tot] ^= lastans, Y[tot] ^= lastans, val[tot] ^= lastans, ins(rt, tot);
		}
		if(op == 2) {
			int l, r, d, u; cin >> l >> d >> r >> u;
			l ^= lastans, d ^= lastans, r ^= lastans, u ^= lastans;
			cout << (lastans = query(rt, l, r, d, u)) << endl;
		}
		if(op == 3) return 0;
	}
	return 0;
}