萌新 KDT 一直 MLE 求助

应该是重构的锅，把重构删掉就不会 MLE 了。

#include <bits/stdc++.h>

#define LL long long
#define DB double
#define PR pair <int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;

const int kN = 5e5 + 5;

int n, tot, rt, cnt, s[kN];
DB al = 0.75;

struct Node {
  int x, y, w;
} d[kN];

bool cmpx(int x, int y) {return d[x].x < d[y].x;}
bool cmpy(int x, int y) {return d[x].y < d[y].y;}

struct Kd {
  int ls[kN], rs[kN], x[kN][2], y[kN][2], siz[kN], sum[kN];
  bool lim;
#define ls(p) ls[p]
#define rs(p) rs[p]

  void Work(int p, int sn) {
    x[p][0] = min(x[p][0], x[sn][0]), x[p][1] = max(x[p][1], x[sn][1]);
    y[p][0] = min(y[p][0], y[sn][0]), y[p][1] = max(y[p][1], y[sn][1]);
  }

  void Pushup(int p) {
    siz[p] = siz[ls(p)] + siz[rs(p)] + 1;
    sum[p] = sum[ls(p)] + sum[rs(p)] + d[p].w;
    x[p][0] = x[p][1] = d[p].x, y[p][0] = y[p][1] = d[p].y;
    if (ls(p)) Work(p, ls(p));
    if (rs(p)) Work(p, rs(p));
  }

  void Build(int l, int r, int &p) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    lim ^= 1;
    nth_element(s + l, s + mid, s + r + 1, lim ? cmpx : cmpy), p = s[mid];
    Build(l, mid - 1, ls(p)), Build(mid + 1, r, rs(p)), Pushup(p);
  }

  void Print(int p) {if (p) Print(ls(p)), s[++cnt] = p, Print(rs(p));}

  void Bal(int &p) {cnt = 0, Print(p), Build(1, cnt, p);}

  void Ins(int k, int &p) {
    if (!p) {p = k, Pushup(p); return;}
    lim ^= 1;
    if (lim) {
      if (d[k].x <= d[p].x) Ins(k, ls(p));
      else Ins(k, rs(p));
    }
    else {
      if (d[k].y <= d[p].y) Ins(k, ls(p));
      else Ins(k, rs(p));
    }
    Pushup(p);
    if ((DB)max(siz[ls(p)], siz[rs(p)]) >= al * siz[p]) Bal(p);
  }

  int Query(int x1, int x2, int y1, int y2, int &p) {
    if (!p || x2 < x[p][0] || x1 > x[p][1] || y2 < y[p][0] || y1 > y[p][1]) return 0;
    if (x1 <= x[p][0] && x[p][1] <= x2 && y1 <= y[p][0] && y[p][1] <= y2) return sum[p];
    int res = 0;
    if (x1 <= d[p].x && d[p].x <= x2 && y1 <= d[p].y && d[p].y <= y2) res = d[p].w;
    return Query(x1, x2, y1, y2, ls(p)) + Query(x1, x2, y1, y2, rs(p)) + res;
  }
} T;

int main() {
  srand(time(0));
  scanf("%d", &n);
  int op, last = 0;
  while (scanf("%d", &op)) {
    if (op == 3) break;
    int x, y, w, x2, y2;
    if (op == 1) {
      scanf("%d%d%d", &x, &y, &w);
      x ^= last, y ^= last, w ^= last;
      //      cout << x << ' ' << y << ' ' << w << endl;
      d[++tot] = (Node) {x, y, w};
      T.Ins(tot, rt);
    }
    else if (op == 2) {
      scanf("%d%d%d%d", &x, &y, &x2, &y2);
      x ^= last, y ^= last, x2 ^= last, y2 ^= last;
      //      cout << x << ' '  << y << ' '  << x2 << ' ' << y2 << endl;
      printf("%d\n", last = T.Query(x, x2, y, y2, rt));
    }
  }
  return 0;
}