思维题随想（一）

标签：思维 支配 分治 leq 随想 dis

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\) 个点对二维数点。

标签：思维,支配,分治,leq,随想,dis
From： https://www.cnblogs.com/hokarikanae/p/17865025.html