zcmimi's blog

arrow_backkdt共8篇文章

avatar
zc
2020-04-16 19:54:00
查看原题

点击跳转

可以看成思维偏序问题

先按第一维优先,相同则继续比较其他维排序(保证之后插入的点不会被之前插入的点的范围覆盖,防止统计的时候漏掉),

f_i=\max{f_j + 1}

剩下三维可以用KDT求出最大的f_j

有两种写法:

  1. 带重构KDT

  2. 先构建完整的KDT,然后把插入当作激活节点

avatar
zc
2020-04-16 18:02:00
查看原题

点击跳转

首先: 构建KDT

对每个点分别进行查询,也就是搜索

直接对KDT进行遍历每次搜索的复杂度是O(n)的,显然TLE

这时我们需要估价函数,在这里也就是:

估算出查询点到子树对应的长方形中的点的"最近距离"

若"最近距离"已经超过了当前答案,就跳过当前子树.

搜索时比较左右子树的"最近距离",先搜索"最近距离"小的

avatar
zc
2020-04-15 14:58:00
查看原题

点击跳转

avatar
zc
2020-04-15 13:42:00
查看原题

点击跳转

avatar
zc
2020-04-15 00:06:00
查看原题

点击跳转

avatar
zc
2020-04-13 20:52:00
查看原题

点击跳转

avatar
zc
2020-04-13 20:06:00
查看原题

点击跳转

k-d tree模板

avatar
zc
2020-03-21 23:31:00
查看原题

点击跳转

允许离线处理

可以看成三维偏序(坐标和时间)

考虑如果要求的点都在当前点的左上方

那么也就是要求x_j\le x_i,y_j\le y_i,time_j\le time_i

x_i+y_i-\max(x_j+y_j)

坐标再旋转并处理三次就可以了

1/1
Search
search