支配点对

我们经常遇到树上或区间上关于 \(x,y\in[l,r]\) 一类的区间统计问题，且通常要求区间内点两两任意匹配并统计总贡献，这个贡献不具有简单可加性。我们往往通过找支配点对可以解决部分这类问题。具体来说，支配点对是一种合法点对 \((l,r)\)，满足其不覆盖更小合法点对 \((l',r')\) 。通过树上启发式合并，我们可以证明这样的点对是 \(O(n\log n)\) 的，因为任意形态树跨子树相邻点配对都是选较小集合然后有只有相邻两个（即常数个）匹配。由于树上启发式合并所需访问集合总大小为 \(O(n\log n)\)，所以点对数目也是。这么说有点抽象，可以前往树上启发式合并博客查看详解。