题目大意，让你支持动态插入，动态查询区间和，强制在线，写(2-D-Tree)
套路，插入(insert),重构(Alpha),(build)一样，注意插入的时候带个(&)符号，对于插入中一路上走过的点，它们都需要改变，重构的时候一样，所以需要传址。
#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10;
#define A 0.75
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
int n,k,rub[MAXN],rs[MAXN];
int tot,top,ls[MAXN],LA;
struct point{
int x[2],cnt;
}p[MAXN],pn;
struct sqr{
int x[3],y[3];
}q;
struct node{
int minn[2],maxn[2],siz,sum;
point c;
}tr[MAXN];
int rt,D;
int operator<(point a,point b){
return a.x[D]<b.x[D];
}
inline void pushup(int x){
int l=ls[x],r=rs[x];
tr[x].siz=tr[l].siz+tr[r].siz+1;
tr[x].sum=tr[l].sum+tr[r].sum+tr[x].c.cnt;
for(register int i=0;i<=1;++i){
tr[x].minn[i]=tr[x].maxn[i]=tr[x].c.x[i];
if(l)tr[x].minn[i]=min(tr[x].minn[i],tr[l].minn[i]),tr[x].maxn[i]=max(tr[x].maxn[i],tr[l].maxn[i]);
if(r)tr[x].minn[i]=min(tr[x].minn[i],tr[r].minn[i]),tr[x].maxn[i]=max(tr[x].maxn[i],tr[r].maxn[i]);
}
}
inline int New(){
if(top)return rub[top--];
else return ++tot;
}
inline int build(int l,int r,int d){
if(l>r)return 0;
int x=New(),mid=l+r>>1;
D=d;nth_element(p+l,p+mid,p+r+1);
tr[x].c=p[mid];ls[x]=build(l,mid-1,d^1);
rs[x]=build(mid+1,r,d^1);pushup(x);return x;
}
inline void clear(int x,int pos){
if(ls[x])clear(ls[x],pos);
p[pos+tr[ls[x]].siz+1]=tr[x].c;rub[++top]=x;
if(rs[x])clear(rs[x],pos+tr[ls[x]].siz+1);
}
inline void check(int &x,int d){
double C=A*(double)(tr[x].siz);
if(C<(double)(tr[ls[x]].siz)||C<(double)(tr[rs[x]].siz)){
clear(x,0);
x=build(1,tr[x].siz,d);
}
}
inline void Ins(int &x,point p,int d){
if(!x){x=New();ls[x]=rs[x]=0;tr[x].c=p;pushup(x);return;}
if(p.x[d]<=tr[x].c.x[d])Ins(ls[x],p,d^1);
else Ins(rs[x],p,d^1);
pushup(x);check(x,d);
}
inline int CKIN(int x,sqr tp){return (!(tr[x].maxn[0]<tp.x[1]||tr[x].minn[0]>tp.x[2]||tr[x].maxn[1]<tp.y[1]||tr[x].minn[1]>tp.y[2]));}
inline int ALLIN(int x,sqr tp){return tr[x].maxn[0]<=tp.x[2]&&tr[x].minn[0]>=tp.x[1]&&tr[x].maxn[1]<=tp.y[2]&&tr[x].minn[1]>=tp.y[1];}
inline int PTIN(point a,sqr tp){return tp.x[2]>=a.x[0]&&tp.x[1]<=a.x[0]&&tp.y[2]>=a.x[1]&&tp.y[1]<=a.x[1];}
inline int query(int x,sqr tp){
if(!x)return 0;
int res=0;
if(ALLIN(x,tp))return tr[x].sum;
else if(!CKIN(x,tp))return 0;
if(PTIN(tr[x].c,tp))res+=tr[x].c.cnt;
res+=query(ls[x],tp);res+=query(rs[x],tp);
return res;
}
int main(){
n=read();
while(1){
register int opt=read();
if(opt==1){
register int x,y,z;
x=read(),y=read(),z=read();
x^=LA,y^=LA,z^=LA;
pn.x[0]=x;pn.x[1]=y;pn.cnt=z;
Ins(rt,pn,0);
}
else if(opt==2){
q.x[1]=read(),q.y[1]=read(),q.x[2]=read(),q.y[2]=read();
q.x[1]^=LA,q.x[2]^=LA,q.y[1]^=LA,q.y[2]^=LA;
LA=query(rt,q);printf("%d
",LA);
}
else if(opt==3)break;
}
return 0;
}