本质思路是，通过可接受复杂度个支配对来表示所有点对。找支配对的核心条件是，在任何情况下其他点对都会被支配对淘汰。找支配对往往有两个限制，一是值是否更优，二是是否更容易满足限制。这相当于一个二维偏序问题，只不过我们要自己找偏序的对象。
在序列上，一般是区间问题，而我们的支配对针对的是一些极小的区间。一般都是考虑前缀最小值 / 最大值，因为如果不是前缀最小值 / 最大值，答案一定会更优。经典问题是求区间 \([l, r]\) 内 \(a_i + a_j\) 的最大值。我们考虑前缀最大值，发现只需要选第一个前缀最大值即可。因为其他的总是可以通过调整为相邻的前缀最大值这种方法来变得更优。序列问题一般都比较简单，很多题都可以规约到这个模型。
接下来我们将探讨更难的树上问题。树上问题虽说形式比较复杂，但是结构比较简明。这种问题一般都与祖先有关，我们的支配对都是基于祖先寻找的。当然，树上的支配对形式是多种多样的，对于不同的题应当灵活应变。
首先是一种最基础的支配对：
P7880 [Ynoi2006] rldcot
枚举 \(\text{lca}(i, j)\)，容易发现支配对是在不同子树内编号最相邻的点对，这样的支配对只有 \(O(n \log n)\) 个。证明是容易的，考虑 dsu on tree 的思想，每次将轻儿子合并到重儿子里面，那么总支配对数就是 dsu on tree 的复杂度，为 \(O(n \log n)\)。求出支配对后 2-side 数颜色即可。
还有一种基于深度的支配对：
QOJ #9676 Ancestors
对于数颜色问题，支配对是同种颜色中编号最相邻的点对，这样数颜色问题就转化为数点问题。显然，每个深度都是独立的，这样我们只需要维护同一深度内每个颜色对应的点集。对 \(x\) 扫描线，每次 \(x \to x + 1\) 时相当于要合并一些点集。采用启发式合并的方法，合并的复杂度是 \(O(n \log n)\) 的（这个复杂度表示的是点的操作次数，要维护支配对的话可能还会多一个 set 的插入删除和 set 上二分的 log）。扫描线的过程中，我们需要支持单点修改和矩形查询，离线下来 cdq 分治即可。由于有 \(O(n \log n)\) 次修改和 \(O(m)\) 次查询，总复杂度为 \(O(n \log^3 n + m \log^2 n)\)。
支配对非常好用！！！