蒟蒻求助K-D Tree

不管是根号重构还是向替罪羊树一样重构都是吸氧之后依然 TLE 4个点 ,感觉不是常数的问题，但是也找不到哪里写假了，求巨佬帮忙 /kk

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int limit=5000;
const double alpha=0.7;
int n;
int lastans=0;
int nowflag=0;
struct node{
  int x;
  int y;
  int val;
  bool operator <(const node &A)const{
    if(nowflag)return x<A.x;
    return y<A.y;
  }
}p[200010];
struct TREE{
  int lson;
  int rson;
  int size;
  int minx;
  int miny;
  int maxx;
  int maxy;
  int x;
  int y;
  int val;
  int sum;
}tree[200010];
int root=0,tot=0,cnt=0;
int stack[200010],top=0;
bool checkin(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){//小的在大的里
  return x1>=X1&&y1>=Y1&&x2<=X2&&y2<=Y2;
}
bool checkout(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){//小的完全在大的外
  return x1>X2||y1>Y2||x2<X1||y2<Y1;
}
void update(int now){
  int ls=tree[now].lson;
  int rs=tree[now].rson;
  tree[now].size=tree[ls].size+tree[rs].size+1;
  tree[now].sum=tree[ls].sum+tree[rs].sum+tree[now].val;
  tree[now].maxx=max(tree[now].x,max(tree[ls].maxx,tree[rs].maxx));
  tree[now].minx=min(tree[now].x,min(tree[ls].minx,tree[rs].minx));
  tree[now].maxy=max(tree[now].y,max(tree[ls].maxy,tree[rs].maxy));
  tree[now].miny=min(tree[now].y,min(tree[ls].miny,tree[rs].miny));
}
int build(int l,int r,int flag){
  if(l>r)return 0;
  int now=stack[top];
  top--;
  int mid=(l+r)/2;
  nowflag=flag;
  nth_element(p+l,p+mid,p+r+1);
  tree[now].x=p[mid].x;
  tree[now].y=p[mid].y;
  tree[now].val=p[mid].val;
  tree[now].lson=build(l,mid-1,flag^1);
  tree[now].rson=build(mid+1,r,flag^1);
  update(now);
  return now;
}
void dfs(int &now){
  stack[++top]=now;
  p[++cnt].x=tree[now].x;
  p[cnt].y=tree[now].y;
  p[cnt].val=tree[now].val;
  if(tree[now].lson)dfs(tree[now].lson);
  if(tree[now].rson)dfs(tree[now].rson);
  now=0;
}
void insert(int &now,int x,int y,int val,int flag){
  if(!now){
    now=++tot;
    tree[now].x=x;
    tree[now].y=y;
    tree[now].sum=tree[now].val=val;
    update(now);
    return;
  }
  if(tree[now].x==x&&tree[now].y==y){
    tree[now].sum+=val;
    tree[now].val+=val;
    return;
  }
  if(flag){
    if(x<=tree[now].x)insert(tree[now].lson,x,y,val,flag^1);
    else insert(tree[now].rson,x,y,val,flag^1);
  }
  else{
    if(y<=tree[now].y)insert(tree[now].lson,x,y,val,flag^1);
    else insert(tree[now].rson,x,y,val,flag^1);
  }
  update(now);
  if(tree[now].size*alpha<tree[tree[now].lson].size||tree[now].size*alpha<tree[tree[now].rson].size){
    cnt=0;
    dfs(now);
    now=build(1,cnt,flag);
  }
}
int query(int now,int x1,int y1,int x2,int y2){
  if(!now)return 0;
  if(checkin(tree[now].minx,tree[now].miny,tree[now].maxx,tree[now].maxy,x1,y1,x2,y2))return tree[now].sum;
  if(checkout(tree[now].minx,tree[now].miny,tree[now].maxx,tree[now].maxy,x1,y1,x2,y2))return 0;
  int ret=0;
  if(checkin(tree[now].x,tree[now].y,tree[now].x,tree[now].y,x1,y1,x2,y2))ret+=tree[now].val;
  ret+=query(tree[now].lson,x1,y1,x2,y2)+query(tree[now].rson,x1,y1,x2,y2);
  return ret;
}
int main(){
  scanf("%d",&n);
  while(1){
    int opt;
    scanf("%d",&opt);
    if(opt==3)break;
    if(opt==1){
      int x,y,a;
      scanf("%d%d%d",&x,&y,&a);
      x^=lastans;
      y^=lastans;
      a^=lastans;
      insert(root,x,y,a,0);
    }
    else{
      int x1,y1,x2,y2;
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      x1^=lastans;
      y1^=lastans;
      x2^=lastans;
      y2^=lastans;
      lastans=query(root,x1,y1,x2,y2);
      printf("%d\n",lastans);
    }
  }
  return 0;
}