悠然w

KDtree

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 洛谷(10) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 矩阵树定理(2) 线段树(4) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

/ 注册

全部文章 / KDtree （共4篇）

KDtree 详解

K:K维 D:dimension 维度网上没找到KDtree在OI和c++方面的详解(可能大佬们都觉得这玩意太简单懒得写？)，累死个人.jpg KDTree相当于多维的线段树算法流程我们要构建一颗二叉树。信息有多维的时候，每往下一层就换一维进行统计。第一层：先竖着切过(7,...

2021-07-18

0 0

P4148 简单题 KDTree

KDtree模板题不会的看这里本题离线的话就是裸的cdq分治强制在线那就按维分割，加入新点的话类似于建树过程,同时记录一下点的范围，以便询问的时候好剪枝为了防止出题人毒瘤(比如让你建的树成了一条链)，你可以每过一段时间重构一下这棵树。代码虽长，但很好写 #include<...

2021-07-18

0 0

CF44G Shooting Gallery KDtree

我们考虑用靶子来匹配射击点，可以把靶子按 \(z\) 从小到大排序后，依次寻找范围内的编号最小的射击点，并将其删除，正确性显然。考虑如何优化这个过程，实际上我们的操作分为两种: \(1.\) 在二维平面内找编号最小的点。 \(2.\) 在二维平面内删除点。可以把射击点建出 \(KDtre...

2020-06-11

0 0

洛谷 P5471 [NOI2019]弹跳 KDtree

我们观察题目后发现这很明显是一道有关最短路的题，首先可以无脑打一个最短路模板上去。 36分 #include<iostream> #include<cstring> #include<cstdio> #include<queue> #define ...

2020-04-02

0 0