支配对

考虑一类问题：给你 \(n\) 个点（序列或树），多次询问，每次询问给你一个大区间 \([L,R]\)，问你对于所有点对 \((x,y)\) 满足 \(L\le x,y\le R\) 有多少种本质不同的 xx（和 \(x,y\) 有关的一个值，下同）或者 xx 的最值是多少。

支配对就是：只考虑 \(\binom n2\) 个点对中的一部分点对，就可以覆盖所有询问的答案（或者说有一些点对不可能出现在答案中）。此时可以降低时间复杂度。

序列支配对（第二类支配对）

先咕了

树上支配对（第一类支配对）

此时上文的 "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 范围内的区间。剩下的维护部分去看历史和吧。

PKUWC 2025 D1T2 Ancestors

给定一棵有根树，多次询问，每次询问给定一个区间 \([l,r]\) 和常数 \(x\)，询问编号 \([l,r]\) 内的节点有多少本质不同的 \(x\) 级祖先。

\(n\le 10^5,~m\le 10^6\)

由于深度不同的节点相互之间是独立的，因此可以分开考虑。考虑对 \(x\) 从小到达进行扫描，过程中会发生合并，询问即区间数颜色。考虑如何处理合并，一层节点显然只会在虚树中的节点处进行合并，再考虑启发式合并暴力单点改颜色，总修改数也是 \(O(n\log n)\)。这样我们就得到了一种 \(O(n\log^3 n+m\log^2 n)\) 的做法。

然而还要虚树，实现太复杂，我们讲点容易实现的。整体思路不变，主要优化合并的过程。考虑长链剖分，对一个节点枚举所有轻链上的节点并将它们合并到重链对应深度的节点上。先跑一遍 dfs 序，然后通过 dfs 序是容易处理的。将合并点对 \((u,v)\) 按照祖先深度 \(x\) 排好序后，再根据等价类的大小进行启发式合并即可。

好像和支配对没啥关系，，