BZOJ 2716 [Violet 3]天使玩偶 ——KD-Tree
2024-09-28 05:25:46
【题目分析】
KD-Tree的例题。同BZOJ2648.
【代码】
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <set> #include <map> #include <string> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std; #define maxn 1000005 #define inf 1e9 int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } struct node{ int mn[2],mx[2],d[2],l,r; int operator [] (int x) {return d[x];} void init() {d[0]=read(); d[1]=read();} }t[maxn],now; int root,D,n,m,tot=0,ans; int dis(node a,node b){return abs(a[1]-b[1])+abs(a[0]-b[0]);} bool operator < (node a,node b){return a[D]<b[D]||(a[D]==b[D]&&a[D^1]<b[D^1]);} void update(int k) { for (int i=0;i<2;++i) { t[k].mn[i]=min(t[k][i],min(t[t[k].l].mn[i],t[t[k].r].mn[i])); t[k].mx[i]=max(t[k][i],max(t[t[k].l].mx[i],t[t[k].r].mx[i])); } } int build(int l,int r,int dir) { int mid=(l+r)/2; D=dir; nth_element(t+l,t+mid,t+r+1); for (int i=0;i<2;++i) t[mid].mn[i]=t[mid].mx[i]=t[mid][i]; if (l<mid) t[mid].l=build(l,mid-1,dir^1); if (r>mid) t[mid].r=build(mid+1,r,dir^1); update(mid); return mid; } void ins(int & k,int dir) { if (!k) { k=++tot; t[k]=now; for (int i=0;i<2;++i) t[k].mn[i]=t[k].mx[i]=t[k][i]; return ; } if (now[dir]<t[k][dir]||(now[dir]==t[k][dir]&&now[dir^1]<t[k][dir^1])) ins(t[k].l,dir^1); else ins(t[k].r,dir^1); update(k); } int get(int k) { if (!k) return inf; int ret=0; for (int i=0;i<2;++i) ret+=max(0,t[k].mn[i]-now[i]); for (int i=0;i<2;++i) ret+=max(0,now[i]-t[k].mx[i]); return ret; } void query(int k) { int dl=get(t[k].l),dr=get(t[k].r),d0=dis(t[k],now); ans=min(ans,d0); if (dl<dr) { if (dl<ans) query(t[k].l); if (dr<ans) query(t[k].r); } else { if (dr<ans) query(t[k].r); if (dl<ans) query(t[k].l); } } int main() { for (int i=0;i<2;++i) t[0].mn[i]=inf,t[0].mx[i]=-inf; n=read();m=read();tot=n; for (int i=1;i<=n;++i) t[i].init(); root=build(1,n,0); while (m--) { int opt=read(); now.init(); if (opt==1) ins(root,0); else { ans=inf; query(root); printf("%d\n",ans); } } }
最新文章
- Jsonp跨域
- LINUX中如何查看某个进程打开的网络链接有多少
- Android PNG透明图片转JPG格式背景变黑
- linux性能监测与优化
- BZOJ 3391 Tree Cutting网络破坏
- [MVC4-基礎] 連動DropDownList - 使用jQuery、JSON
- uva10954 - Add All(multiset功能)
- Ioc容器BeanPostProcessor-Spring 源码系列(3)
- java 如何自定义异常 用代码展示 真心靠谱
- Springmvc导出Excel(maven)
- eclipse项目两个红点
- 微信小程序设置全局字体
- 学习fortran77基础语法
- 路径不对 导致FileNotFoundError: [WinError 2] 系统找不到指定的文件, 问题解决办法
- [笔记] print函数进阶
- GoogleCpp风格指南 8)格式 _part1
- selenium - 获取断言信息
- mybatis 表情存储报错问题解决
- http协议基础教程
- KM算法(理解篇)