这东西其实就是高维二叉树？（反正我只会二维的）
大概就是把一个高维矩形按每一维分，一个点（及其子树）就表示一个高维区间，乱搞一下，就……没了？
1 //BZOJ4066 "简单"题
2 //维护N*N矩形，初始全为0，支持两种操作：
3 //1.将格子(x,y)的数字加上A
4 //2.求(x1,y1)到(x2,y2)这个矩形内的数字和
5 //3.结束程序
6 //由于平衡性，每5000次插入就暴力重构一次
7 #include<algorithm>
8 #include<iostream>
9 #include<cstring>
10 #include<cstdio>
11 #include<cmath>
12 using namespace std;
13 int D;
14 struct kdnode{
15 int ls,rs,num,v,d[2],mi[2],mx[2];
16 int &operator [](int x){
17 return d[x];
18 }
19 friend bool operator <(kdnode a,kdnode b){
20 return a[D]<b[D];
21 }
22 }t[200001],rb[200001],s;
23 int n,op,x1,yy,x2,y2,v,rt=0,tot=0,R=5000,ans=0;
24 bool inside(int x1,int yy,int x2,int y2,int x3,int y3,int x4,int y4){
25 return x1<=x3&&x2>=x4&&yy<=y3&&y2>=y4;
26 }
27 bool outside(int x1,int yy,int x2,int y2,int x3,int y3,int x4,int y4){
28 return x1>x4||x2<x3||yy>y4||y2<y3;
29 }
30 void pushup(int u){
31 int l=t[u].ls,r=t[u].rs;
32 for(int i=0;i<=1;i++){
33 t[u].mi[i]=t[u].mx[i]=t[u][i];
34 if(l)t[u].mi[i]=min(t[u].mi[i],t[l].mi[i]);
35 if(l)t[u].mx[i]=max(t[u].mx[i],t[l].mx[i]);
36 if(r)t[u].mi[i]=min(t[u].mi[i],t[r].mi[i]);
37 if(r)t[u].mx[i]=max(t[u].mx[i],t[r].mx[i]);
38 }
39 t[u].num=t[l].num+t[r].num+t[u].v;
40 }
41 int query(int u,int x1,int yy,int x2,int y2){
42 int ret=0;
43 if(!u)return 0;
44 if(inside(x1,yy,x2,y2,t[u].mi[0],t[u].mi[1],t[u].mx[0],t[u].mx[1]))return t[u].num;
45 if(outside(x1,yy,x2,y2,t[u].mi[0],t[u].mi[1],t[u].mx[0],t[u].mx[1]))return 0;
46 if(inside(x1,yy,x2,y2,t[u][0],t[u][1],t[u][0],t[u][1]))ret+=t[u].v;
47 ret+=query(t[u].ls,x1,yy,x2,y2)+query(t[u].rs,x1,yy,x2,y2);
48 return ret;
49 }
50 void ins(int &u,bool d){
51 if(!u){
52 u=++tot;
53 t[u][0]=t[u].mi[0]=t[u].mx[0]=s[0];
54 t[u][1]=t[u].mi[1]=t[u].mx[1]=s[1];
55 }
56 if(s[0]==t[u][0]&&s[1]==t[u][1]){
57 t[u].v+=s.v;
58 t[u].num+=s.v;
59 return;
60 }
61 if(s[d]<t[u][d])ins(t[u].ls,d^1);
62 else ins(t[u].rs,d^1);
63 pushup(u);
64 }
65 int rebuild(int l,int r,bool d){
66 if(l>r)return 0;
67 int mid=(l+r)/2;
68 D=d;
69 nth_element(rb+l,rb+mid,rb+r+1);
70 t[mid]=rb[mid];
71 t[mid].ls=rebuild(l,mid-1,d^1);
72 t[mid].rs=rebuild(mid+1,r,d^1);
73 pushup(mid);
74 return mid;
75 }
76 int main(){
77 scanf("%d",&n);
78 for(;;){
79 scanf("%d",&op);
80 if(op==1){
81 scanf("%d%d%d",&x1,&yy,&v);
82 x1^=ans;
83 yy^=ans;
84 v^=ans;
85 s[0]=x1;
86 s[1]=yy;
87 s.num=s.v=v;
88 ins(rt,0);
89 if(tot==R){
90 for(int j=1;j<=tot;j++){
91 rb[j]=t[j];
92 }
93 rt=rebuild(1,tot,0);
94 R+=5000;
95 }
96 }else if(op==2){
97 scanf("%d%d%d%d",&x1,&yy,&x2,&y2);
98 x1^=ans;
99 yy^=ans;
100 x2^=ans;
101 y2^=ans;
102 printf("%d
",(ans=query(rt,x1,yy,x2,y2)));
103 }else break;
104 }
105 return 0;
106 }