rpmtdq
洛谷 P9058 [Ynoi2004] rpmtdq
洛谷传送门 类比 P9062 [Ynoi2002] Adaptive Hsearch&Lsearch 处理区间最近点对的思路,尝试只保留可能有贡献的点对。 处理树上路径容易想到点分治。设点 \(u\) 到分治中心的距离为 \(a_u\)。我们有 \(\text{dis}(u, v) \le a_u ......
[Ynoi2004] rpmtdq 题解
人生第一发 \(Ynoi\) 的题, 写一篇题解庆祝一下 传送门 我们可以发现, 对于二元组 \((x, y)\) , 若存在一个 \(dist(i, j) \le dist(x, y), x < i < j < y\) 那么答案肯定不是二元组 \((x, y)\) 我们可以考虑把这些肯定不是的点剔 ......