萌新初学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;
} 

有没有做过的人知道为什么总是 MLE 啊

只过了第一个点 /kk

把 if(bad(id)) rebuild(id); 注释掉可以拿到 60 分的好成绩