%%%神仙\(SJY\)

题目大意：

一个二维平面，有两种操作：

\(1.\)增加一个点\((x,y)\)

\(2.\)询问距离\((x,y)\)曼哈顿最近的一个点有多远

\(n,m\le 300 000,x_i,y_i\le 1 000 000\)

咱目前不会\(k-d\ tree\)先不提了，只讲\(cdq\)分治做法

考虑一个点如果在令一个点的右上方时，两点之间的曼哈顿距离可以转化为两个点到原点的曼哈顿距离之差，我们可以用这个方法加\(cdq\)分治求出每个询问左下角的点最近的曼哈顿距离

\(cdq\)分治时先按\(x\)排序，按\(y\)归并，按\(tim\)树状数组就可以秒了

那别的方向怎么办？

把整个矩阵转三次，然后跑\(4\)次\(cdq\)不就完了

代码懒得放了，挺裸的自己脑补吧

最新文章

1. 懵懂的js原型
2. Uva1515 Pool construction
3. 保存知乎收藏夹功能的NodeJS版本
4. 【crunch bang】国内源
5. jquery easyui读取json文件乱码
6. mac os 系统密码正确的 但是进不了系统
7. loading-show-hide
8. asp.net等项目编译失败的原因之不能写入
9. shell复习笔记----入门知识
10. const用法
11. TDirectory.GetLastAccessTime获取指定目录最后访问时间
12. hdu 1875
13. ASPX的Timer位置没放正确，导致整页刷新，而不是UpdatePanel里的内容刷新。
14. 51nod 1376 最长递增子序列的数量(线段树)
15. 在虚拟机上利用宿主机共享目录编译linux程序
16. django 多对多 增 删 改 查
17. js发送get 、post请求的方法简介
18. IDC：UPS（不间断电源）
19. 领扣-5 最长回文子串 Longest Palindromic Substring MD
20. AD采样的一个例子

热门文章

1. WPF 绑定属性 XAML 时间格式化
2. vscode源码分析【九】窗口里的主要元素
3. SqlServer ----- 根据查询语句创建视图
4. jQuery 源码分析(十一) 队列模块 Queue详解
5. C#使用Emgu CV来进行图片人脸检测
6. 【踩坑系列】VS2019提示 ' the package could not be found in c\users\username\nuget\packages\. '
7. zTree插件的应用
8. Java生鲜电商平台-高并发核心技术订单与库存实战
9. 02Javascript变量和数据类型
10. uni-app聊天室|vue+uniapp仿微信聊天实例|uniapp仿微信App界面