$O((n+m)\log n)$ 题解 by ChatGPT

GPT-6 Pro 只能做到 $O(n\log n+m\log^2 n)$ ？玩的太差了！可以进一步做到 确定性的 $O((n+m)\log n)$ 总时间、$O(n\log n)$ 空间，并支持在线询问，单次最坏 $O(\log n)$。

上一版多出来的对数有两个来源：块内仍然进行“最大孩子链对任意祖先链”的查询，以及每处理一个块，都要重新倍增寻找路径与块的交点。这两处都能降到 $O(1)$，而且预处理仍然只需要 $O(n\log n)$。

一、保留排名窗口，但让每个块只花常数时间

仍然采用前面的特殊中心作为固定根，记 $h_u$ 为子树高度，叶子的高度为 $0$；$d_u$ 为深度；$w_u$ 为产物类型编号，编号越大，产物越大；$\rho_u=1+\#{v:w_v>w_u}$。直接孩子类型的降序序列可以用来比较产物，并且高度较大的类型一定较大。特殊根下，换根公式为：若 $y$ 是 $x$ 的祖先，则 $f(x,y)=d_x-d_y+1$；否则，$f(x,y)=\rho_y+\#{v\in P_x:w_v\le w_y}$，其中 $P_x$ 是固定根到 $x$ 的路径。这里沿用解题报告中的基础归约。([QOJ][1])

相同类型必须保留并列排名，所有逆序对也都采用严格大于；不能把相同类型人为拆成不同名次。([QOJ][2])

对一次询问，令 $l=\operatorname{LCA}(s,t)$，两条臂为 $\mathcal A=(l,s]$、$\mathcal B=(l,t]$，长度分别为 $S,T$。以下讨论跨臂贡献，另一方向交换两条臂即可。

记 $I(U,V)=\#{(u,v):u\in U,v\in V,w_u>w_v}$。对于目标 $y\in\mathcal B$，令 $p_y=\#{u\in\mathcal A:w_u>w_y}$。当根位于 $\mathcal A$ 上从上往下数的第 $i$ 个点时，有 $f(a_i,y)=\rho_y+\max(0,i-p_y)$。

令 $q$ 为 $\mathcal B$ 上满足 $\rho_y\le r$ 的前缀长度，$q_0$ 为满足 $f(s,y)\le r$ 的前缀长度，并令 $\mathcal D$ 为第 $q_0+1$ 至第 $q$ 个点组成的祖先链。跨臂贡献为

$$ C(\mathcal A,\mathcal B) = Sq_0+|\mathcal D|r-\sum_{y\in\mathcal D}\rho_y +I(\mathcal A,\mathcal D). $$

只有最后一项需要处理路径逆序对。对于每个 $y\in\mathcal D$，都有 $\rho_y\le r< f(s,y)$。根路径上的高度严格递减，而 $w_v\le w_y$ 必然推出 $h_v\le h_y$，所以这样的根路径点至多有 $h_y+1$ 个。因此，$\rho_y\le r< f(s,y)\le\rho_y+h_y+1$。

按 $h_y+1$ 的最高二进制位分层。在高度尺度为 $H=2^k$ 的层内，$H\le h_y+1< 2H$，于是所有需要处理的目标都满足 $r-2H<\rho_y\le r$。这是每层只需要考虑常数个块的原因。

具体分块方法不变：将这一层的顶点按类型从大到小排列，相同类型作为不可拆分的一组。出现次数至少为 $H$ 的类型单独形成纯类型块；其余类型组依次累积，达到 $H$ 个顶点时结束当前块，遇到纯类型块或者这一层结束时也将当前块收尾。

每个普通块的大小小于 $2H$，同一层中任意两个相邻块的大小之和至少为 $H$。设 $\mathcal D$ 在这一层中的最高点和最低点分别落在第 $i,j$ 个块。二者的排名差小于 $2H$，所以中间完整经过的块的总大小也小于 $2H$。若有四个完整中间块，将它们两两配对，总大小至少为 $2H$，矛盾。因此，每层至多涉及五个块。

对于其中一个块 $B$，令 $\mathcal D_B=\mathcal D\cap B$、$\mathcal A_B=\mathcal A\cap B$，再令 $\mathcal A_{>B}$ 为 $\mathcal A$ 上类型大于整个块的点。因为类型组没有跨块，有 $I(\mathcal A,\mathcal D_B)=|\mathcal A_{>B}|\cdot|\mathcal D_B|+I(\mathcal A_B,\mathcal D_B)$。

所以，每次询问只涉及 $O(\log n)$ 个块。接下来需要同时完成两件事：块内逆序对 $O(1)$，路径与块的交点也 $O(1)$。

二、同时拆开两条路径，块内逆序对做到 $O(1)$

对每个非叶点，固定选择一个类型最大的孩子，称为选中孩子。选中边将原树分成若干条互不相交的链。因为选中孩子的高度恰好小 $1$，每条链都一直延伸到叶子，链头高度为 $L-1$ 时，链长就是 $L$。

考虑一个块的诱导森林。由于祖先链上的类型严格递减，一条祖先链与一个块的交集总是连续的。而且，若某个点的一个孩子留在块内，那么它的选中孩子也一定留在块内：选中孩子的类型介于这个孩子与父亲之间。

因此，块内只有一个孩子的点，通向该孩子的边必然是选中边。

称块内至少有两个孩子的点为分叉点。对块内顶点 $x$，记 $S_x$ 为所在连通分量的根到 $x$ 的路径，$a(x)$ 为这条路径上最深的分叉点，允许为 $x$ 自身；不存在时记为 $0$，并约定 $S_0$ 为空。

把 $S_x$ 拆成 $S_{a(x)}$ 与后缀 $C_x$。后缀不包含分叉点本身，因此 $C_x$ 一定是一段连续的选中链。

上一版只预处理了一个方向，然后留下“链对任意路径”的查询。这次对每个分叉点 $a$，同时预处理两行：

$F_a(x)=I(S_a,S_x)$，以及 $G_a(x)=I(S_x,S_a)$。

若块大小为 $s_B$、分叉点数为 $b_B$，表长为 $O(s_Bb_B)$。构建一行时，标记 $S_a$，按完整类型组扫描块内顶点，分别求出标记点中严格更大、严格更小的数量，再沿块内森林做前缀累加即可。一行只需要 $O(s_B)$ 时间。

所有块的总表长仍然是线性的。对于高度尺度为 $H$ 的一个块内分叉点 $u$，选择一个不是选中孩子的块内孩子 $v$。这个 $v$ 是一条选中链的链头，而 $h_v+1\ge H$，所以该链至少有 $H$ 个点。不同分叉点对应不同的链头，所选的链互不相交，因此 $\sum_B H_Bb_B\le n$。

普通块满足 $s_B< 2H_B$；纯类型块内部没有树边，更不可能有分叉点。于是 $\sum_B s_Bb_B< 2n$。两张表一起也只需要 $O(n)$ 时间和空间。

现在设 $a=a(x)$、$b=a(y)$。将两边都拆开，有

$$ I(S_x,S_y) = F_a(y)+G_b(x)-F_a(b)+I(C_x,C_y). $$

前三项直接查表，剩下的已经不是链对任意路径，而是两段选中链之间的逆序对。

这个问题可以通过类型树的 LCA 在 $O(1)$ 内解决。

建立类型树：每个不同类型是一个顶点，非叶类型的父亲是它最大的孩子类型，叶类型为根。类型树中的深度恰好等于原类型的高度。把每个结点的孩子按类型编号递增排列，并求出 DFS 序。

在同一高度上，类型的大小顺序与类型树的 DFS 顺序一致。原因是比较两个类型时，首先比较最大的孩子，也就是先比较类型树中的父亲；父亲相同时，再由兄弟之间的类型编号决定顺序。

考虑两段选中链 $C,D$，高度范围分别为 $[a,b]$、$[c,d]$，顶部类型分别为 $U,V$。它们在各自的每个高度上恰好有一个点。

高度不同的点对只需比较高度。对于 $D$ 中高度为 $j$ 的点，若 $j

只剩同高度的比较。令 $z=\operatorname{LCA}_{\mathrm{type}}(U,V)$，$\ell$ 为 $z$ 的深度。对于两段链都包含的高度 $j$：

当 $j\le\ell$ 时，两边类型相同；当 $j>\ell$ 时，两边类型不同，其大小关系由 $U,V$ 的 DFS 顺序决定，并且不再随 $j$ 改变。

所以，同高度部分只需补上 $[\operatorname{tin}(U)>\operatorname{tin}(V)]\max(0,\min(b,d)-\max(a,c,\ell+1)+1)$。