KDTree求助 去重构TLE 重构MLE

/*
 * Author:Ehundategh
 * Update:2023/10/17
 * Title:K-Dimension Tree.cpp
 * You steal,I kill
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LSon Node[Now].LeftS
#define RSon Node[Now].RightS
const double Alpha=0.9851872;
#define MAXN 200010
using namespace std;
struct node{
    int X,Y;
    int Value;
    int LeftS,RightS;
    int Size,Sum;
    int Up,Down,Left,Right,Dimension;
}Node[MAXN];
int LastAns=0,Root,cnt=0,Order[MAXN],cnl=0,n,Option,In1,In2,In3,In4,In5;
bool cmpx(int a,int b){return Node[a].X<Node[b].X;}
bool cmpy(int a,int b){return Node[a].Y<Node[b].Y;}
int New(int X,int Y,int Value){
    Node[++cnt]={X,Y,Value};
    return cnt;
}
void Update(int Now){
    Node[Now].Size=Node[LSon].Size+Node[RSon].Size+1;//和二叉搜索树一样更新Size
    Node[Now].Sum=Node[LSon].Sum+Node[RSon].Sum+Node[Now].Value;//更新权值总和，方便查询
    Node[Now].Left=Node[Now].Right=Node[Now].X;
    Node[Now].Up=Node[Now].Down=Node[Now].Y; //更新上下左右边界
    if(LSon){
        Node[Now].Left=min(Node[Now].Left,Node[LSon].Left);
        Node[Now].Right=max(Node[Now].Right,Node[LSon].Right);
        Node[Now].Up=max(Node[Now].Up,Node[LSon].Up);
        Node[Now].Down=min(Node[Now].Down,Node[LSon].Down);
    }
    if(RSon){
        Node[Now].Left=min(Node[Now].Left,Node[RSon].Left);
        Node[Now].Right=max(Node[Now].Right,Node[RSon].Right);
        Node[Now].Up=max(Node[Now].Up,Node[RSon].Up);
        Node[Now].Down=min(Node[Now].Down,Node[RSon].Down);
    }
}
int Build(int Left,int Right,int Dimension){
    if(Left>Right) return 0;
    int Mid=(Left+Right)>>1;
    if(Dimension==2){
        nth_element(Order+Left,Order+Mid,Order+Right+1,cmpx); Node[Order[Mid]].Dimension=2;
    }
    else nth_element(Order+Left,Order+Mid,Order+Right+1,cmpy); Node[Order[Mid]].Dimension=3;
    Node[Order[Mid]].LeftS=Build(Left,Mid,Dimension^1);
    Node[Order[Mid]].RightS=Build(Mid+1,Right,Dimension^1);
    Update(Order[Mid]);
    return Order[Mid];
}
void Slap(int Now){
    if(!Now) return;
    Slap(LSon);
    Order[++cnl]=Now;
    Slap(RSon);
}
void Rebuild(int &Now){
    cnl=0;
    int D=Node[Now].Dimension;
    Slap(Now);
    Now=Build(1,cnl,D);
}
bool Not_Balance(int Now){
    return Alpha*Node[Now].Size<=(double)max(Node[LSon].Size,Node[RSon].Size);
}
void Insert(int &Now,int Target){
    if(!Now){
        Now=Target;
        Update(Now);
        return;
    }
    if(Node[Now].Dimension==2){
        if(Node[Target].X<Node[Now].X) Insert(LSon,Target);
        else Insert(RSon,Target);
    }
    else{
        if(Node[Target].Y<Node[Now].Y) Insert(LSon,Target);
        else Insert(RSon,Target);
    }
    Update(Now);
    if(Not_Balance(Now)) Rebuild(Now);
}
int Query(int Now,int Left,int Right,int Up,int Down){
    if(!Now||Right<Node[Now].Left||Left>Node[Now].Right||Up<Node[Now].Down||Down>Node[Now].Up) return 0;
    if(Node[Now].Left>=Left&&Node[Now].Right<=Right&&Node[Now].Up<=Up&&Node[Now].Down>=Down) return Node[Now].Sum;
    int Ret=0;
    if(Node[Now].X>=Left&&Node[Now].X<=Right&&Node[Now].Y<=Up&&Node[Now].Y>=Down) Ret+=Node[Now].Value;
    return Ret+Query(LSon,Left,Right,Up,Down)+Query(RSon,Left,Right,Up,Down);
}
int main(){
    scanf("%d",&n);
    while(1){
        scanf("%d",&Option);
        if(Option==3) return 0;
        if(Option==1){
            scanf("%d%d%d",&In1,&In2,&In3);
            In1^=LastAns;
            In2^=LastAns;
            In3^=LastAns;
            New(In1,In2,In3);
            Insert(Root,cnt);
        }
        if(Option==2){
            scanf("%d%d%d%d",&In1,&In2,&In3,&In4);
            In1^=LastAns;
            In2^=LastAns;
            In3^=LastAns;
            In4^=LastAns;
            printf("%d\n",LastAns=Query(Root,In1,In3,In4,In2));
        }
    }
    return 0;
}