博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ4066】简单题(KD-Tree)
阅读量:4842 次
发布时间:2019-06-11

本文共 3356 字,大约阅读时间需要 11 分钟。

【BZOJ4066】简单题(KD-Tree)

题面

题解

如果这题不卡空间,并且不强制在线的话

显然可以用\(CDQ\)分治做

但是它又卡空间又强制在线,于是我们欢快的来用\(KD-Tree\)吧。

\(KD-Tree\)维护每一个点,每次询问的时候

判断询问的矩形和当前矩形的交
如果全部覆盖直接加上所有的和
如果没有交则直接返回
如果有部分交则递归处理。

我用了两种方案防止\(KD-Tree\)被卡

第一种:定时重构。大概就是每插入\(10000\)次后就重构一次

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define ll long long#define RG register#define MAX 100200#define mid o#define ls (t[o].ch[0])#define rs (t[o].ch[1])#define cmin(a,b) (a
b?a:a=b)inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}const double alpha=0.762333;int D;struct Node{int d[2],v;}a[MAX];bool operator<(Node a,Node b){return a.d[D]
>1;D=nd; nth_element(&a[l],&a[mid],&a[r+1]); t[o].a=a[mid]; if(l
mid)rs=Build(mid+1,r,nd^1);else rs=0; pushup(o);return o;}void insert(int &o,int nd,Node a){ if(!o){o=tot;t[o].a=a;pushup(o);return;} if(t[o].a.d[nd]
=x1&&t[o].a.d[0]<=x2&&t[o].a.d[1]>=y1&&t[o].a.d[1]<=y2) ret+=t[o].a.v; if(ls) { int d=checksame(t[ls],x1,x2,y1,y2); if(d==1)ret+=t[ls].sum; if(d==2)ret+=Query(ls,x1,x2,y1,y2); } if(rs) { int d=checksame(t[rs],x1,x2,y1,y2); if(d==1)ret+=t[rs].sum; if(d==2)ret+=Query(rs,x1,x2,y1,y2); } return ret;}int N,rt;int main(){ N=read(); int lans=0,opt,x,y,A,x1,y1,x2,y2; while(233) { opt=read(); if(opt==3)break; if(opt==1) { x=read()^lans,y=read()^lans,A=read()^lans; insert(rt,0,a[++tot]=(Node){x,y,A}); if(tot%10000==0)rt=Build(1,tot,0); } else { x1=read()^lans,y1=read()^lans,x2=read()^lans,y2=read()^lans; printf("%d\n",lans=Query(rt,x1,x2,y1,y2)); } }}

第二种:类似替罪羊树,当不满足平衡因子时,把子树拍掉重构。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define ll long long#define RG register#define MAX 200200#define ls (t[o].ch[0])#define rs (t[o].ch[1])#define cmin(a,b) (a
b?a:a=b)inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}const double alpha=0.75;int D;struct Node{int d[2],v;}a[MAX];bool operator<(Node a,Node b){return a.d[D]
>1;D=nd; nth_element(&a[l],&a[mid],&a[r+1]); int o=NewNode(); t[o].a=a[mid]; if(l
mid)rs=Build(mid+1,r,nd^1);else rs=0; pushup(o);return o;}void kill(int o){if(ls)kill(ls);a[++Num]=t[o].a;Q[++top]=o;if(rs)kill(rs);}void checker(int &o,int nd){ if(alpha*t[o].size
=x1&&t[o].a.d[0]<=x2&&t[o].a.d[1]>=y1&&t[o].a.d[1]<=y2) ret+=t[o].a.v; if(ls) { int d=checksame(t[ls],x1,x2,y1,y2); if(d==1)ret+=t[ls].sum; if(d==2)ret+=Query(ls,x1,x2,y1,y2); } if(rs) { int d=checksame(t[rs],x1,x2,y1,y2); if(d==1)ret+=t[rs].sum; if(d==2)ret+=Query(rs,x1,x2,y1,y2); } return ret;}int N,rt;int main(){ N=read(); int lans=0,opt,x,y,A,x1,y1,x2,y2; while(233) { opt=read(); if(opt==3)break; if(opt==1) { x=read()^lans,y=read()^lans,A=read()^lans; insert(rt,0,(Node){x,y,A}); } else { x1=read()^lans,y1=read()^lans,x2=read()^lans,y2=read()^lans; printf("%d\n",lans=Query(rt,x1,x2,y1,y2)); } }}

转载于:https://www.cnblogs.com/cjyyb/p/9069206.html

你可能感兴趣的文章
人工神经网络 Artificial Neural Network
查看>>
N/A version is not installed yet 解决办法
查看>>
软考错题合集之14-11-AM
查看>>
大二暑假周记第三篇
查看>>
poj3286_How many 0's?
查看>>
Kubernetes Service 模板
查看>>
Quartus II& Nios II 出错解决办法
查看>>
[leetcode-110]balanced-binary-tree
查看>>
Oracle 日期查询
查看>>
python diango学习笔记一
查看>>
ActiveMQ
查看>>
linux下实现nginx安装实现端口区分,域名区分
查看>>
CentOS7.2环境下安装Nginx
查看>>
MFC动态创建控件及其消息响应函数
查看>>
团队作业_1_博客1(分工理解)
查看>>
mybatis 一对多和一对一写法注意事项
查看>>
三、使用vscode在docker中debug
查看>>
设计模式之 面向对象的养猪厂的故事,C#演示(一)
查看>>
分页及字母筛选
查看>>
Expressions are not allowed at the top level
查看>>