这东西其实就是高维二叉树?(反正我只会二维的)
大概就是把一个高维矩形按每一维分,一个点(及其子树)就表示一个高维区间,乱搞一下,就……没了?
1 //BZOJ4066 "简单"题 2 //维护N*N矩形,初始全为0,支持两种操作: 3 //1.将格子(x,y)的数字加上A 4 //2.求(x1,y1)到(x2,y2)这个矩形内的数字和 5 //3.结束程序 6 //由于平衡性,每5000次插入就暴力重构一次 7 #include8 #include ); 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\n",(ans=query(rt,x1,yy,x2,y2))); 103 }else break; 104 } 105 return 0; 106 }9 #include 10 #include 11 #include 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 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] 1