1. 洛谷 P9678 [ICPC2022 Jinan R] Tree Distance
一个套路：支配点对。在本题中的意思是，若 $x_1\leq x_2\leq y_2\leq y_1$ 且 $dis(x_2,y_2)\leq dis(x_1,y_1)$，那么 $(x_2,y_2)$ 就支配了 $(x_1,y_1)$，后者对答案一定没有贡献。考虑点分治。设当前分治中心为 \(t\)，分治子树内所有点到中心的距离为 \(d_x\)，考虑某个点 \(i\)，则只有满足 \(d_x\leq d_i\) 的 \(x\) 构成的集合 \(S\) 中 \(i\) 的前驱后继才可能是支配点对。
于是找出 \(d_x\) 后，按 \(x\) 升序/降序扫描，单调栈一下就行。然后对这 \(n\log n\) 个点对二维数点。