这东西其实就是高维二叉树?(反正我只会二维的)

大概就是把一个高维矩形按每一维分,一个点(及其子树)就表示一个高维区间,乱搞一下,就……没了?

 //BZOJ4066 "简单"题
//维护N*N矩形,初始全为0,支持两种操作:
//1.将格子(x,y)的数字加上A
//2.求(x1,y1)到(x2,y2)这个矩形内的数字和
//3.结束程序
//由于平衡性,每5000次插入就暴力重构一次
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int D;
struct kdnode{
int ls,rs,num,v,d[],mi[],mx[];
int &operator [](int x){
return d[x];
}
friend bool operator <(kdnode a,kdnode b){
return a[D]<b[D];
}
}t[],rb[],s;
int n,op,x1,yy,x2,y2,v,rt=,tot=,R=,ans=;
bool inside(int x1,int yy,int x2,int y2,int x3,int y3,int x4,int y4){
return x1<=x3&&x2>=x4&&yy<=y3&&y2>=y4;
}
bool outside(int x1,int yy,int x2,int y2,int x3,int y3,int x4,int y4){
return x1>x4||x2<x3||yy>y4||y2<y3;
}
void pushup(int u){
int l=t[u].ls,r=t[u].rs;
for(int i=;i<=;i++){
t[u].mi[i]=t[u].mx[i]=t[u][i];
if(l)t[u].mi[i]=min(t[u].mi[i],t[l].mi[i]);
if(l)t[u].mx[i]=max(t[u].mx[i],t[l].mx[i]);
if(r)t[u].mi[i]=min(t[u].mi[i],t[r].mi[i]);
if(r)t[u].mx[i]=max(t[u].mx[i],t[r].mx[i]);
}
t[u].num=t[l].num+t[r].num+t[u].v;
}
int query(int u,int x1,int yy,int x2,int y2){
int ret=;
if(!u)return ;
if(inside(x1,yy,x2,y2,t[u].mi[],t[u].mi[],t[u].mx[],t[u].mx[]))return t[u].num;
if(outside(x1,yy,x2,y2,t[u].mi[],t[u].mi[],t[u].mx[],t[u].mx[]))return ;
if(inside(x1,yy,x2,y2,t[u][],t[u][],t[u][],t[u][]))ret+=t[u].v;
ret+=query(t[u].ls,x1,yy,x2,y2)+query(t[u].rs,x1,yy,x2,y2);
return ret;
}
void ins(int &u,bool d){
if(!u){
u=++tot;
t[u][]=t[u].mi[]=t[u].mx[]=s[];
t[u][]=t[u].mi[]=t[u].mx[]=s[];
}
if(s[]==t[u][]&&s[]==t[u][]){
t[u].v+=s.v;
t[u].num+=s.v;
return;
}
if(s[d]<t[u][d])ins(t[u].ls,d^);
else ins(t[u].rs,d^);
pushup(u);
}
int rebuild(int l,int r,bool d){
if(l>r)return ;
int mid=(l+r)/;
D=d;
nth_element(rb+l,rb+mid,rb+r+);
t[mid]=rb[mid];
t[mid].ls=rebuild(l,mid-,d^);
t[mid].rs=rebuild(mid+,r,d^);
pushup(mid);
return mid;
}
int main(){
scanf("%d",&n);
for(;;){
scanf("%d",&op);
if(op==){
scanf("%d%d%d",&x1,&yy,&v);
x1^=ans;
yy^=ans;
v^=ans;
s[]=x1;
s[]=yy;
s.num=s.v=v;
ins(rt,);
if(tot==R){
for(int j=;j<=tot;j++){
rb[j]=t[j];
}
rt=rebuild(,tot,);
R+=;
}
}else if(op==){
scanf("%d%d%d%d",&x1,&yy,&x2,&y2);
x1^=ans;
yy^=ans;
x2^=ans;
y2^=ans;
printf("%d\n",(ans=query(rt,x1,yy,x2,y2)));
}else break;
}
return ;
}

最新文章

  1. WCF 安全性 之 Windows
  2. 入侵本地Mac OS X的详细过程 转自https://yq.aliyun.com/articles/22459?spm=5176.100239.blogcont24250.10.CfBYE9
  3. UITableViewCell自定义
  4. 命令行参数 main()函数设计
  5. Spring的定时任务配置(转)
  6. phpMyAdmin的用户名和密码丢了怎么办?
  7. Html4与Html5的关键区别
  8. PHP session 失效不传递的解决办法
  9. 模板:优先队列(priority_queue)
  10. Response乱码时的处理方法
  11. 【LightOJ1282】Leading and Trailing(数论)
  12. CentOS 7 Redis安装配置
  13. 【10】Cookie和Session
  14. 2018-2019-2 20165325 《网络对抗技术》 Exp5:MSF基础应用
  15. rest-framework的认证组件
  16. Java使用Sockt进行通信(2)
  17. java -jar 命令
  18. SQL HAVING 子句使用
  19. vue 实战报错解决方案
  20. [Git01]Pro Git 第三章 分支 读书笔记

热门文章

  1. 第一次接触Arduino
  2. iOS开发-测量APP启动耗时
  3. ZBrush为电影制作设计独特的生物概念
  4. [修改高通平台WIFI MAC 地址] &amp; [adb over wifi]
  5. 一个完整的Flexbox指南(转载)
  6. vim配置C++开发环境 win10
  7. ZOJ 3911Prime Query [素数处理 + 线段树]
  8. centos 登陆跳转指定目录
  9. [读书笔记] R语言实战 (十三) 广义线性模型
  10. S5PV210 三个Camera Interface/CAMIF/FIMC的区别