O(nlogn)支配对_成型笔记

$\cal O(n \log n)$ 支配对

初始有 $n$ 个对象，两两可以产生一个贡献，每次问区间点对贡献的合并。

如果维护两两贡献，则复杂度为 $\Theta(n^2)$，无法接受。

但有的时候题目有性质，只需要计算 $\Theta(n\log n)$ 个点对贡献就可以覆盖 $\Theta(n^2)$ 对的贡献，这些点对叫做支配集。

通常找到支配集后原问题变得平凡。

第一类支配对

两两对象产生一个贡献，总共产生 $\Omega(n^2)$ 对贡献，但是这些贡献中本质不同的只有 $\cal O(n)$ 种。

例如区间在树上两两 $\rm lca$ 的贡献合并，$\rm lca$ 只有本质不同的 $n$ 种，我们通常可以考虑树上启发式合并。

有点抽象，看题吧。

P7880 [Ynoi2006] rldcot

给定一棵带权树，定义深度为到根的边权和，$q$ 次询问 $[l,r]$ 中两两点对 $(x,y)$（$x,y$ 可以相等）有多少种不同的 ${\rm dep}(\rm{lca}(x,y))$。

$n\le10^5,q\le5\times 10^5,{500 \rm \ ms}$。

考虑把询问区间视为二维平面上的点，最后查点，现在我们需要考虑 每个点对 对 整个平面 的贡献。

先考虑边权为 $1$ 的情况，考虑树上启发式合并，每次把两棵子树合并的时候产生的贡献一定是 ${\rm dep}(x)$，而我们发现点对把包含它的点对给支配了（一个数在小区间中出现了 就没有必要关心 它是否在包含这个区间的区间出现了）。

所以我们枚举小子树 $x$，每次在大子树中询问前驱后继，我们就得到了 $\Theta({\rm siz}(x))$ 个区间，我们把包含这些区间的区间的并集全部 $+1$，你发现这就是在做矩形面积并。

同样的，每层产生的所有矩形都要并起来再加，因为它们的 $\rm dep$ 相同，发现这都是 $\text{2-side}$ 矩形，所以并起来后的矩形量和原矩形数同阶。

现在有边权了，也好办，直接对每个深度对应的所有矩形并起来再加即可，问题转化为先大量矩形 $+1$，再大量求单点值。

扫描线 + 树状数组即可，$\Theta(n\log^2 n+m\log n)$。

P8528 [Ynoi2003] 铃原露露

给定一棵有根树和一个排列 $a$，共 $q$ 次询问，每次询问给出 $l,r$，询问有多少个二元组 $L,R$，满足 $l\le L\le R\le r$，且对任意 $L\le a_x\le a_y\le R$，有 $x,y$ 在树上的最近公共祖先 $z$ 满足 $L\le a_z\le R$。

$1\le n,q\le 2\times 10^5$。

其实就是问每个区间有多少个子区间满足所有点对 $\rm lca$ 都在自己内啦。

还是把 $(l,r)$ 视作二维平面上的点，令两个点 $x<y$，若 ${\rm lca}(x,y)\in[x,y]$，则该点对不会造成影响，否则假设 $p={\rm lca}(x,y)<x$，则 $l\in(p,x],r\in[y,n]$ 的点对全部没有贡献，$p>y$ 的时候类似。

假设我们已经考虑了 $n^2$ 个点对了，那就变成矩形覆盖矩形查 $0$ 的个数，可以扫描线 + 区间加区间减（但保证任意时刻非负）区间 $0$ 的个数历史和线段树即可。

现在考虑支配问题，树上启发式合并的好处就是你可以知道 $\rm lca$ 和其中一个点 $x$。

若 ${\rm lca}<x$，则我们要询问最小的 $y\ge x$ 和最大的 $y\le x$，因为这样可以让影响的范围最大化，包裹住所有 $({\rm lca},x)$ 点对造成的贡献，${\rm lca}>x$ 是同理的。

我们顺便提一嘴区间 $0$ 的个数历史和咋做：

节点维护 $(m,c,p)$ 表示区间最小值是 $m$，当前区间有 $c$ 个 $m$，以及 $c$ 的历史和；标记维护 $(a,o)$ 表示区间加多少，区间历史和要加几次 $c$。

$$\begin{aligned}(m,c,p)\cdot(M,C,P)&\to(\min(m,M),c[m\le M]+C[M\le m],p+P)\\(m,c,p)+(a,o)&\to(m+a,c,p+oc)\\(a,o)+(A,O)&\to(a+A,o+O)\end{aligned}$$

一贯的套路：还需要注意只有左右区间 $\min$ 是真正的 $m$ 才可以把 $o$ 传下去，但该节点的 $m$ 已经被区间加改过了，所以其实判断的是左右区间的 $\min$ 是否是二者间的最小值即可。

（需要注意传下去之后就不能比较了，所以需要提前确定是否需要往左右传，还有 modify 中下传的规则和 down 中应该是一样的。）

其实你可以看出来这类问题使用支配对并不是在第一步，通常是先思考 $n^2$ 个点对全都考虑的时候怎么做然后再考虑支配问题。

第二类支配对

两两对象产生一个贡献，总共产生 $\Omega(n^2)$ 对贡献，但是这些贡献中本质不同的有 $\Omega(n^2)$ 种。

常见的题型：区间内两两算个东西然后求 $\min$ 或 $\max$。

支配集通常有这两种形式：

• 对每个 $i$，可以用数据结构高效找出 $\cal O(\log n)$ 个 $j$，这些 $(i,j)$ 的贡献支配了所有 $(i,1),(i,2),\cdots,(i,n)$ 的贡献。
• 对一维分治时，假设对大小 $n$ 的问题进行分治，会产生 $\cal O(n)$ 对跨过分治中线的贡献，这些贡献支配了本来两边产生的 $\Omega(n^2)$ 对贡献，一般这种问题会对信息那一维分治，不对序列分治。

仍然很抽象，我们看题：

这两个题是对每个 $i$，找出 $\log n$ 个 $j$。

CF1793F Rebrending & P5926 [JSOI2009] 面试的考验 & CF765F Souvenirs

给定序列，$q$ 次询问区间最小差。

这三道题各自有独特的限制，但有一个通用的做法。

这题的支配关系很明显，一个点对在你之内且差比你小那你就被支配了。

先考虑每个位置往前统计值比它小的数的贡献，值比它大的贡献可以翻转值域再做一遍。

考虑当前在 $i$，往前找到了最近的 $j$ 满足 $a_j<a_i$，再次找一个没有被支配的对 $(i,k)$，也就相当于在 $a_i,a_j$ 间插一个 $a_k$，必须满足 $a_i-a_k<a_k-a_j$，也就是说 $a_k$ 必须更靠近 $a_i$ 一点，否则 $(i,k)$ 就会被 $(j,k)$ 支配，这样跳一次值域至少缩小了一半。

我们看找的过程，要找满足某个值域条件 $[l,r[$ 的某个位置 $i$ 前的最靠后的位置，我们可以用主席树，每次在第 $i$ 个版本的值域线段树上区间求 $\max$。

CodeChef MINXORSEG

给定序列，$q$ 次询问区间最小 $\rm xor$。

类似地，考虑 $k<j<i$，若 $(i,k)$ 不被 $(i,j),(j,k)$ 支配，则必须保证 $(a_i\oplus a_k<a_j\oplus a_k)\wedge (a_i\oplus a_k<a_i\oplus a_j)$。

考虑三者的二进制表示 $\rm lcp$，可以证明在未顶满的情况下，只要有其中两个 $\rm lcp$ 等长，则第三个必然比这两个长。

所以只要 $(i,k)$ 的贡献更优，每次限制的 $\rm lcp$ 都至少增加一位，然后就变成上面那个题了。

---

下面就是分治部分了。

感觉分治只是一种形式，什么东西都能往里套。

通常使用分治消去复杂的一维，剩下的留给简单维。

CF1793F Rebrending & P5926 [JSOI2009] 面试的考验 & CF765F Souvenirs

想不到吧这三个也能用分治做。

对值域分治，每次按照中位数分治下去，每次统计跨过 $\rm mid$ 的点对。

设 $b_i=|{\rm mid}-a_i|$，则 $|a_i-a_j|=b_i+b_j$。

然后你发现所有点对都可以自由组合，即使是同侧的，因为组合它们会使答案变劣。

于是你就得到了一个新问题：有若干点对 $(i,b_i)$，你需要在每个范围 $[l,r]$ 中选 $i,j\in [l,r]$ 使得 $b_i+b_j$ 最小。

其实就是区间最小值和次小值的和，如果这是一个大问题我们肯定直接 $\rm RMQ$ 做了，但我们不能在分治层中枚举询问。

设 $i<j<k$，若 $(i,k)$ 不被支配则 $b_i+b_k<b_i+b_j\wedge b_i+b_k<b_j+b_k$，即 $b_i<b_j,b_k<b_j$，也就是说我们的支配集是两端是区间最小值的那些区间。

被一个错误的思路困扰了半个小时，我觉得这样的支配集是 $\Omega(n^2)$ 的，构造了一个金字塔状序列，然后我觉得左边选一个右边选一个就可以构成一个合法点对了。

有一个朴素的思路是按照 $b_i$ 从小到大排序，每次加入一个数 $i$ 到序列中时找到前驱后继 $j,k$，则 $(i,j),(i,k)$ 均为支配点对，且不漏。

你可以把从小往大加换成从大往小删，配上链表求出前驱后继。

求出所有分治的所有 $\Theta(n\log n)$ 个点对后，回到全局开始处理询问，对于每个 $(i,j)(i<j)$，枚举右端点到 $j$ 时在树状数组上加入 $i$ 的贡献即可。

这其实是可以强制在线的，只需要把树状数组变成主席树就好。

复杂度 $\Theta(n\log^2 n)$。

P9058 [Ynoi2004] rpmtdq

给定一棵树，边权全正，区间询问树上最近距离。

$n\le2\times 10^5,q\le 10^6$。

顺便提一嘴区间树上最远距离，就是虚树直径，根据直径的性质我们在线段树上每个节点维护直径的两个端点即可快速合并。

然后你发现就是把上面的值域分治换成点分治就完了。

P8078 [WC2022] 秃子酋长

$q$ 次询问区间排序后相邻元素在原序列的位置的差的绝对值的和。

$n,q\le 5\times 10^5$。

回滚莫队做法略。

考虑分治，每次处理跨过中点的询问。

把两边分别排序，分别统计左边内部的贡献，右边内部的贡献，左对右的贡献，右对左的贡献。

考虑右边每两个排序后相邻的位置 $i,j$，找到左边原序列中最靠右的 $a_k\in[a_i,a_j]$ 的位置 $k$。

设要处理一个询问区间 $[L,R]$，当 $R\ge \max(i,j)$ 时，若 $L\in (k,{\rm mid}]$ 则贡献为 $|i-j|$，否则 $L\in[l,k]$ 时贡献为 $i+j$，因为你并不知道在左边经历了几次跳跃，所以你干脆撒手不管，在左边处理没有处理的贡献。

对称地，在左边做相同的操作，但当覆盖 $k$ 时贡献变成了 $-i-j$，这对应上面没处理的贡献。

对最大值和最小值的处理是相似的。

这里支配对的体现其实就是把关心:“$(i,j)$ 被哪几个数打断”变成了关心“$(i,j)$ 有没有被数打断"。

P7883 平面最近点对（加强加强版）

单次求平面最近点对。

$n\le4\times 10^5$。

先考虑一维的情况，在值域上分治，如果想要做到比子问题还要优秀还要跨过中线，则每边至多一个数符合，如果有两个数则子问题答案会更优，矛盾。

然后是二维，经过一些神秘论证可以发现需要的点不超过 $6$ 个，于是枚举一个点暴力枚举后继即可。

P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

区间平面最近点对。

实际上还是利用了平面最近点对中选取当前答案 $d$，将整个图分为 $d\times d$ 的网格，则每个格中只有 $\le 1$ 个点，更新答案枚举周围方格。

似乎有一点屎山，之后拿来练码力吧。