KDtree
KDtree(K-Dimension tree)适用于处理与距离和位置有关的多维点对问题,本质上就是经过剪枝的暴力,难点在于估价函数的设计
k远点对
题目链接:https://www.luogu.com.cn/problem/P4357
题意:给出n个二维点,求出第K远点对的距离.其中$n\in(1,1e6),K\in(1,1e2)$
分析:按照最直接的思路,求出每一对点之间的距离再排序,时间复杂度会达到$O(n^2)$.
在这个暴力的过程中,很多点对都不会产生贡献,考虑合并处理区间优化.对点集排序,对于当前选择的两个点$a_l,a_r$,如果$x_l,x_r$与$y_l,y_r$的距离和小于当前答案,那么在$x_l,x_r$之间且$y_l,y_r$之间的点对一定对答案没有影响.
考虑用矩形来分割整个平面,再用点对递归分割子平面.每次选取一个维度上的中点,对当前子平面进行再划分,这样就构造出一颗二叉树.由于每个维度的区间中点不同,每次用nth_element得到,避免反复sort.KDtree的构造时间复杂度是$O(nlogn)$,与一般二分数据结构相同.
至于划分的维度,可以选用方差最大的维度,这样数据分布的比较开,可以保证树高,树的形态会更平衡.为了省事也可以按维度顺序轮流选择.
树上的每个结点维护一个矩形区间,表示子树在平面上的范围.
查询时,用当前点来更新答案.预测左右子树与询问点的最大距离,如果最大情况下对答案都没有贡献,就没有必要进入子树了.利用预测值还有一个优化,根据左右子树预测值的大小关系,决定子树的访问顺序.
单次询问的平均复杂度为$O(n^{(1-\frac{1}{k})})$,具体分析可以看这篇博客:https://blog.csdn.net/qq_50332374/article/details/123242226. 需要注意的是,kdtree的单次查询最坏复杂度仍然是$O(n)$的,可能被刻意构造的数据卡死.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//估价函数
ll edis(node &p,PNT &pn){
ll res=0;
For(i,0,1){
ll t=max(abs(p.mx[i]-pn.x[i]),abs(p.mn[i]-pn.x[i]));
res+=t*t;
}
return res;
}
void qry(node &p,PNT &pn){
if(!p.sz)return ;
if(K||dis(p.pn,pn)>=ans)add(p.pn,pn);
ll dl=0,dr=0;
if(p.ls)dl=edis(ar[p.ls],pn);
if(p.rs)dr=edis(ar[p.rs],pn);
if(dl>=dr){
if(K||dl>=ans) qry(ar[p.ls],pn);
if(K||dr>=ans) qry(ar[p.rs],pn);
}
else{
if(K||dr>=ans) qry(ar[p.rs],pn);
if(K||dl>=ans) qry(ar[p.ls],pn);
}
}
JZPFAR
题目链接:https://www.luogu.com.cn/problem/P2093
题意:给出一个二维点集,m次查询,每次询问到指定的点距离第K大的点的标号
分析:和上题处理方法相同.不过这题比较卡常,可以设置全局变量避免反复传参,把维度的循环展开成判断.最后还是没卡成,一发O2才过.
[SDOI2010]捉迷藏
题目链接:https://www.luogu.com.cn/problem/P2479
题意:给出一个二维点集,求出点集中的任意一点到其他点的最大和最小的距离之差的最小值
分析:需要注意最大值和最小值的估价函数的写法.最大估价考虑到较远的矩形边界的距离,而最小估价考虑到矩形内部的距离.1
2
3
4
5
6
7
8
9
10
11
12
13
14ll emax(node &p,PNT &pn){
ll res=0;
For(i,0,1)res+=max(abs(p.mx[i]-pn.x[i]),abs(p.mn[i]-pn.x[i]));
return res;
}
ll emin(node &p,PNT &pn){
ll res=0;
For(i,0,1){
ll t1=max(0ll,pn.x[i]-p.mx[i]);
ll t2=max(0ll,p.mn[i]-pn.x[i]);
res+=t1+t2;
}
return res;
}
Mokia 简单题
题目链接:https://www.luogu.com.cn/problem/P4390
https://www.luogu.com.cn/problem/P4148
题意:在一个$n*n$矩阵中,单点修改,矩形范围查值.操作总数不超过$4e5$
分析:这次要求动态加点,如果直接把新点找个叶子挂上,可能会出现树结构的不平衡,要考虑用平衡树的方法维护kdtree.
由于kdree的每一层严格对应一个维度的划分,treap类随机乱选和splay改变父子关系肯定不行,只能考虑替罪羊树的局部重构.
精确查询的操作无法用估价函数剪枝,考虑用矩形覆盖的观点合并计算.
如果当前矩形被目标矩形全包,那么直接返回整个矩形的和.如果两者不相交,所有的子矩形也一定不产生共享,直接返回.
友情提醒一下两个矩形不相交只要满足任意一维不相交 (我太菜了卡了好久).
1 | //被完全覆盖 |