支配对
考虑一类问题：给你 \(n\) 个点（序列或树），多次询问，每次询问给你一个大区间 \([L,R]\)，问你对于所有点对 \((x,y)\) 满足 \(L\le x,y\le R\) 有多少种本质不同的 xx（和 \(x,y\) 有关的一个值，下同）或者 xx 的最值是多少。
支配对就是：只考虑 \(\binom n2\) 个点对中的一部分点对，就可以覆盖所有询问的答案（或者说有一些点对不可能出现在答案中）。此时可以降低时间复杂度。
序列支配对（第二类支配对）
P5926 [JSOI2009] 面试的考验
不妨设点对是 \(i<j\) 且 \(a_i<a_j\) 的形式。对一个 \(i\) 找到右边第一个更大的 \(j_0\)，考察 \(j_0\) 右边哪些 \(j\) 可能和 \(i\) 有贡献：如果 \(a_j\ge \frac{a_i+a_{j_0}}{2}\)，那么 \((j,j_0)\) 比 \((i,j_0)\) 更优，因此这样的 \(j\) 没有贡献。找到 \(j_0\) 右边第一个 \([a_i+1,\frac{a_i+a_{j_0}}{2}-1]\) 的 \(j_1\)，发现 \(j_1\) 右边离 \(a_{j_1}\) 更近的 \(j\) 也不会和 \(i\) 产生贡献，以此类推找到 \(j_2,j_3\cdots\) 发现 \(j_i\to j_{i+1}\) 值域至少减半，因此支配对数量只有 \(O(n\log V)\) 个。
树上支配对（第一类支配对）
此时上文的 "xx" 是一个与 \(x,y\) 的 \(\operatorname{LCA}\) 有关的东西。通过启发式合并我们可以证明，极小且 \(\operatorname{LCA}\) 不同的点对只有 \(O(n\log n)\) 对。极小指的是，不可能只将 \(x\) 向右移动或将 \(y\) 向左移动，而 \(\operatorname{LCA}\) 不变。考虑启发式合并的过程，我们钦定当前节点 \(u\) 为 \(\operatorname{LCA}\)，然后枚举所有轻儿子子树中的节点，查询它们在前面子树中，节点编号的前驱后继。这样显然是 \(O(n\log n)\) 的。
P7880 [Ynoi2006] rldcot
“Range LCA Depth Count On Tree”
先跑出所有支配对，然后二维数颜色即可。
P8528 [Ynoi2003] 铃原露露
考虑什么样的区间是不合法的。一个区间不合法当且仅当存在一个点对 \((x,y)\)，\(z=\operatorname{LCA}(x,y)\)，\((x,y)\) 在区间内，\(z\) 不在区间内。枚举 \(\operatorname{LCA}\) 节点 \(z\)，极小的 \((x,y)\) 也只有 \(O(n\log n)\) 个。找到一组 \((x,y,z)\) 后，会 ban 掉一个 3-side 范围内的区间。剩下的维护部分去看历史和吧。
P9678 [ICPC 2022 Jinan R] Tree Distance
考虑点分治，对于一个点 \(u\)，考虑跨过分治中心的其它子树内的两个节点 \(x,y\) 满足 \(p<x<y\)，发现如果 \(d(x)+d(y)<d(p)+d(y)\) 即 \(d(x)<d(p)\)，那么 \((p,y)\) 就没有贡献。因此对每个 \(p\) 不妨只让它匹配 \(d(x)<d(p)\) 中编号大于 \(p\) 且最小以及编号小于 \(p\) 且最大的两个点，容易发现这样的点只有 \(O(n\log n)\) 个。