【kd-tree】bzoj4066 简单题
2024-09-01 13:49:32
同p1176。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 200011
#define KD 2//ά¶ÈÊý
int qp[2][2];
int n,root=1,m;
bool dn;
struct Node
{
int minn[KD],maxx[KD],p[KD],w,ch[2],sumv;
void Init()
{
for(int i=0;i<KD;++i)
minn[i]=maxx[i]=p[i];
sumv=w;
}
}T[N];
void Clear()
{
for(int i=1;i<=n;++i)
T[i].ch[0]=T[i].ch[1]=/*T[i].sumv=T[i].minn[0]=T[i].minn[1]=T[i].maxx[0]=T[i].maxx[1]=*/0;
}
void Update(int rt)
{
T[rt].sumv=T[rt].w;
for(int i=0;i<2;++i)
if(T[rt].ch[i])
{
T[rt].sumv+=T[T[rt].ch[i]].sumv;
for(int j=0;j<KD;++j)
{
T[rt].minn[j]=min(T[rt].minn[j],T[T[rt].ch[i]].minn[j]);
T[rt].maxx[j]=max(T[rt].maxx[j],T[T[rt].ch[i]].maxx[j]);
}
}
}
bool operator < (const Node &a,const Node &b){return a.p[dn]<b.p[dn];}
int Buildtree(int l=1,int r=n,bool d=0)
{
dn=d;
int m=(l+r>>1);
nth_element(T+l,T+m,T+r+1);
T[m].Init();
if(l!=m) T[m].ch[0]=Buildtree(l,m-1,d^1);
if(m!=r) T[m].ch[1]=Buildtree(m+1,r,d^1);
Update(m);
return m;
}
void Insert(int rt=root,bool d=0)
{
bool f=(T[n].p[d]>T[rt].p[d]);
if(T[rt].ch[f]) Insert(T[rt].ch[f],d^1);
else T[rt].ch[f]=n;
Update(rt);
}
int ans;
void Query(int rt=root)
{
if(T[rt].p[0] >= qp[0][0] && T[rt].p[0] <= qp[1][0]
&& T[rt].p[1] >= qp[0][1] && T[rt].p[1] <= qp[1][1])
ans+=T[rt].w;
for(int i=0;i<2;++i)
if(T[rt].ch[i]
&& T[T[rt].ch[i]].maxx[0] >= qp[0][0] && T[T[rt].ch[i]].minn[0] <= qp[1][0]
&& T[T[rt].ch[i]].maxx[1] >= qp[0][1] && T[T[rt].ch[i]].minn[1] <= qp[1][1])
{
if(T[T[rt].ch[i]].minn[0] >= qp[0][0] && T[T[rt].ch[i]].maxx[0] <= qp[1][0]
&& T[T[rt].ch[i]].minn[1] >= qp[0][1] && T[T[rt].ch[i]].maxx[1] <= qp[1][1])
ans+=T[T[rt].ch[i]].sumv;
else
Query(T[rt].ch[i]);
}
}
int op[N],X1[N],Y1[N],X2[N],Y2[N],Vs[N];
int main()
{
// freopen("bzoj4066.in","r",stdin);
// freopen("bzoj4066.out","w",stdout);
// for(int i=1;i<=1000000;++i);
scanf("%d",&m); m=0;
while(1)
{
++m;
scanf("%d",&op[m]);
if(op[m]==3)
{
--m;
break;
}
if(op[m]==1)
{
scanf("%d%d%d",&X1[m],&Y1[m],&Vs[m]);
++n;
}
else
scanf("%d%d%d%d",&X1[m],&Y1[m],&X2[m],&Y2[m]);
}
int blo=(int)sqrt((double)n*log2((double)n));
n=0;
for(int i=1;i<=m;++i)
{
if(op[i]==1)
{
++n;
T[n].p[0]=X1[i]; T[n].p[0]^=ans;
T[n].p[1]=Y1[i]; T[n].p[1]^=ans;
T[n].w=Vs[i]; T[n].w^=ans;
// printf("Insert%d:(%d,%d):%d\n",n,T[n].p[0],T[n].p[1],T[n].w);
T[n].Init();
if(n>1)
Insert();
if(blo==1 || blo==0 || n%blo==0)
{
Clear();
Buildtree();
root=(1+n>>1);
}
}
else
{
qp[0][0]=X1[i]; qp[0][0]^=ans;
qp[0][1]=Y1[i]; qp[0][1]^=ans;
qp[1][0]=X2[i]; qp[1][0]^=ans;
qp[1][1]=Y2[i]; qp[1][1]^=ans;
ans=0;
if(n)
Query();
printf("%d\n",ans);
}
}
}
最新文章
- Java 教程整理:基础、项目全都有
- ActiveMQ实现负载均衡+高可用部署方案
- 基本套接字编程(7) -- udp篇
- 被废了的display:box弹性盒模型
- 工作中常用的Linux命令:mkdir命令
- mac10.9+php5.5.15+brew0.9.5的安装
- Python自动化 【第三篇】:Python基础-集合、文件操作、字符编码与转码、函数
- Sql server之路 (三)添加本地数据库SDF文件
- Learning Vector
- ACM大数模板(支持正负整数)
- Java的λ表达(lambda)
- 用css制作一个三角形箭头
- python网络编程之单线程之间的并发
- Nginx负载均衡搭建(Window与Linux)
- Gitlab管理网页老是500错误?增加物理内存,增加cpu吧
- laravel compact的用法
- iOS快捷代码块
- 20165319 《JAVA程序设计》第一周学习总结
- ubuntu18.04 安装mysql server
- 实现AJAX的基本步骤
热门文章
- 闲话JavaScript与Cookies
- codeforces 719C. Efim and Strange Grade
- remove computer from join with powershell
- [01]url请求到渲染
- mavne问题解决---Dynamic Web Module 2.3 or newer
- 动态规划:树形DP
- codeforces613B - Skills &;&;金中市队儿童节常数赛
- 【BZOJ】1799: [Ahoi2009]self 同类分布
- javascript学习3
- Symfony2之创建一个简单的web应用 Symfony2——创建bundle