GPT-6 Astra xhigh 只能做到 $\widetilde O(n^{5/4})$？玩的太差了！可以降到 总时间 polyog，并且支持在线询问：预处理 $O(n\log n)$，单次询问 $O(\log^2 n)$，空间 $O(n\log n)$。

前情提要：https://qoj.ac/problem/17306/discussion/2621

一、保留排名限制，找出真正的查询窗口

沿用前面的类型编号：$w_u$ 越大，产物越大；相同产物编号相同。产物比较可以等价地改为比较直接孩子类型的降序序列，并且高度较大的类型一定较大。选择合适的直径中心作为固定根 $o$，可以得到之前使用的换根公式。这些基础归约与公开解题报告一致。(QOJ)

具体地，单中心时直接选择它；双中心时，断开中心边，比较两侧分别以中心为根的类型，选择较大一侧的中心。记 $h_u$ 为固定根下的子树高度，叶子高度为 $0$；$d_u$ 为深度，$P_u$ 为 $o$ 到 $u$ 的路径；$\rho_u=1+\#{v:w_v>w_u}$。这里必须保留并列排名，不能把相同类型拆成不同的名次。(QOJ)

换根后，若 $y\in P_x$，则 $f(x,y)=d_x-d_y+1$；否则有 $f(x,y)=\rho_y+\#{v\in P_x:w_v\le w_y}$。

考虑最难的 $o_x=o_y=1$。设 $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}$。对于 $\mathcal B$ 上的目标 $y$，令 $p_y=\#{u\in\mathcal A:w_u>w_y}$。当根是 $\mathcal A$ 上第 $i$ 个点时，有 $f(a_i,y)=\rho_y+\max(0,i-p_y)$。

因此，$\rho_y>r$ 的目标没有贡献；其余目标贡献 $\min(S,p_y+r-\rho_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). $$

前面的边界与前缀和都容易处理。上一版把最后一项进一步转成任意根路径逆序对；这次不再这么做，而是观察 $\mathcal D$ 中的点为什么会留下来。

对于每个 $y\in\mathcal D$，都有 $\rho_y\le r< f(s,y)$。另一方面，根路径上的高度严格递减，而 $w_v\le w_y$ 必然推出 $h_v\le h_y$，所以一条根路径上满足 $w_v\le w_y$ 的点至多有 $h_y+1$ 个。于是得到关键限制：

$$ \boxed{\qquad \rho_y\le r< f(s,y)\le \rho_y+h_y+1, \qquad y\in\mathcal D. \qquad} $$

现在按 $h_y+1$ 分倍增层。对于某个 $H=2^k$，只考虑 $H\le h_y+1< 2H$ 的目标，那么它们全部满足 $r-2H< \rho_y\le r$。

也就是说，高度尺度为 $H$ 时，真正需要处理的目标，只落在长度小于 $2H$ 的排名窗口中。

两条臂交换后同样处理。同臂部分仍然是等差数列求和：设 $\alpha,\beta$ 分别是两条臂上满足 $\rho_y\le r$ 的前缀长度，令 $E(L,r)=\sum_{i=1}^{L}\min(r,i+1)$。取 $k=\min(L,r-1)$，则 $E(L,r)=k(k+3)/2+(L-k)r$。完整答案就是 $1+E(S,r)+E(T,r)+\alpha(\alpha+1)/2+\beta(\beta+1)/2+C(\mathcal A,\mathcal B)+C(\mathcal B,\mathcal A)$。

二、按高度分层，再按完整的类型组分块

将全部顶点按 $w$ 从大到小排列，相同类型放在一起。由于高度决定类型大小的第一层顺序，同一个倍增高度层 $H\le h_u+1< 2H$ 对应这个序列中的一段连续区间。

在每一层内部，按下面的方式分块，始终不拆开相同类型。

一个类型若出现至少 $H$ 次，就单独形成一个纯类型块。其余类型组依次加入当前块，累计顶点数达到 $H$ 时结束这个块；遇到纯类型块之前，以及这一层结束时，把尚未结束的块收尾。

于是，普通块的大小小于 $2H$。不足 $H$ 的普通块只可能出现在一个大纯类型块之前，或者这一层的结尾，因此同一层内任意两个相邻块的大小之和至少为 $H$。纯类型块可能很大，但其中所有点类型相同，块内严格逆序对恒为 $0$。

下面证明一次查询在每层最多涉及 $5$ 个块。

令 $\mathcal D_H$ 为 $\mathcal D$ 在当前高度层中的部分。它仍是一段祖先链，设其最高点与最低点分别为 $u,v$。根据上一节的限制，$\rho_v-\rho_u< 2H$。

从包含 $u$ 的块到包含 $v$ 的块，中间完整经过的所有块，都位于这两个类型组的起始排名之间，因此这些完整块的顶点总数小于 $2H$。如果有四个完整块，将它们两两配对，每对大小之和至少为 $H$，总数就至少为 $2H$，矛盾。

所以最多有三个完整的中间块，加上两个端点块，一共至多五块。这个证明也覆盖了巨大的并列类型组：它不会被拆成许多小块。

还需要把 $\mathcal A$ 上不在当前块中的点排除。设当前块为 $B$，目标片段为 $\mathcal D_B$；令 $\mathcal A_{>B}$ 为 $\mathcal A$ 上类型位于整个块之前的点，$\mathcal A_B=\mathcal A\cap B$。因为类型组没有被拆开，前者的类型严格大于块内所有类型，块之后的类型则不可能贡献，所以

$I(\mathcal A,\mathcal D_B)=|\mathcal A_{>B}|\cdot|\mathcal D_B|+I(\mathcal A_B,\mathcal D_B)$。

第一项只需沿祖先链查找边界。至此，任务变成：

预处理每个块，使得同一块内两段祖先链的逆序对可以在 $O(\log n)$ 时间内回答。

每次原询问只有 $O(\log n)$ 个高度层，每层至多五块，所以这个块内数据结构就足以得到单次 $O(\log^2 n)$。

三、块内只预处理分叉点，总表长甚至是线性的

在原树的每个非叶点，固定选择一个类型最大的孩子，称为选中孩子。选中边把原树分成若干条互不相交的链。沿每条这样的链，高度每次恰好下降 $1$；若链头是 $v$，整条链的长度就是 $h_v+1$。

考虑一个块的诱导森林。由于祖先链上的类型严格递减，一个块与一条祖先链的交集总是连续的。

还有一个重要性质：若 $u$ 和它的某个孩子 $v$ 都在块内，那么 $u$ 的选中孩子也一定在块内，因为选中孩子的类型介于 $w_u$ 和 $w_v$ 之间，而整个类型组不会跨块。因此，块内只有一个孩子的点，通向这个孩子的边必然是选中边。

称块内至少有两个孩子的点为分叉点。对块内顶点 $x$，记 $S_x$ 为所在块内连通分量的根到 $x$ 的路径。对于每个分叉点 $a$，预处理一整行 $M_B(a,x)=I(S_a,S_x)$，其中 $x$ 遍历块内所有顶点。

若块大小为 $s_B$，分叉点数量为 $b_B$，这些表需要 $s_Bb_B$ 个数。每一行也能在 $O(s_B)$ 时间内求出：标记 $S_a$，按类型从大到小扫描整个块，按相同类型整组处理，求出每个点 $x$ 对应的 $g_x=\#{u\in S_a:w_u>w_x}$，再沿块内森林计算 $M_B(a,x)=M_B(a,\operatorname{parent}_B(x))+g_x$。

这里最容易误判的是所有块的总开销。实际上，全部表加起来只有 $O(n)$ 项。

对于高度尺度为 $H$ 的一个块内分叉点 $u$，选择一个不是选中孩子的块内孩子 $v$。由于 $v$ 也在当前高度层中，有 $h_v+1\ge H$；而 $v$ 恰好是一条选中边链的链头，这条链至少有 $H$ 个点。

不同分叉点选出的链头不同，对应的这些链互不相交。所以，将所有高度层、所有块一起求和，也有 $\sum_B H_Bb_B\le n$。普通块满足 $s_B< 2H_B$，纯类型块没有分叉点，故

$$ \sum_B s_Bb_B < 2\sum_B H_Bb_B \le 2n. $$

这不是把每层的线性开销再乘一个对数，而是对所有层统一得到的线性界。

接下来说明怎样利用这些表回答块内查询。令 $a(x)$ 为 $S_x$ 上最深的分叉点，允许是 $x$ 自身；没有分叉点时记为空。把 $S_x$ 拆成 $S_{a(x)}$ 与后缀 $C_x$，其中 $C_x$ 不包含 $a(x)$。

后缀 $C_x$ 是一段连续的最大类型孩子链。注意必须排除分叉点本身：从分叉点走向当前分支的第一步，不一定走向选中孩子。

于是，$I(S_x,S_y)=M_B(a(x),y)+I(C_x,S_y)$，其中空分叉点对应的表项视为 $0$。任意两段块内祖先链之间的逆序对，都可以用四个这样的前缀查询相减得到。

现在只剩最后一个基本操作：一段最大类型孩子链，与任意祖先链之间的逆序对，如何做到 $O(\log n)$？

建立一棵类型树：每个不同类型是一个顶点，非叶类型的父亲是它最大的孩子类型，叶类型作为根。类型在这棵树中的深度正好等于它的高度。

把每个类型结点的孩子按类型编号递增排列，求类型树的 DFS 区间 $[\operatorname{in}(t),\operatorname{out}(t)]$。同一深度的类型，其 DFS 顺序恰好与类型大小顺序一致：不同父亲时先比较最大的孩子类型；父亲相同时，顺序由兄弟之间的类型编号决定。

设最大类型孩子链 $C$ 的顶部为 $c$，高度范围为 $[a,b]$。它恰好在每个高度上有一个点。对于高度位于 $[a,b]$ 内的点 $v$，链上同高度的类型是 $w_c$ 在类型树中的对应祖先，因此链上这个类型严格大于 $w_v$，当且仅当 $\operatorname{out}(w_v)<\operatorname{in}(w_c)$。

所以，对任意根路径 $P_z$，有

$$ \begin{aligned} I(C,P_z) ={}&(b-a+1)\#\{v\in P_z:h_v< a\}\\ &+\sum_{\substack{v\in P_z\\a\le h_v\le b}}(b-h_v)\\ &+\#\{v\in P_z:a\le h_v\le b,\ \operatorname{out}(w_v)< \operatorname{in}(w_c)\}. \end{aligned} $$

第一项是链中所有点都比 $v$ 高的情况。第二项统计高度严格更大的链中点。第三项补上同高度时的严格类型比较。

根路径上的高度严格递减，所以高度范围 $[a,b]$ 对应一段祖先链。用倍增找到两个边界后，前两项由深度和高度前缀和得到；最后一项则在这段祖先链上查询 $\operatorname{out}(w_v)$ 的一维前缀计数。

具体地，沿原树建立以类型树 $\operatorname{out}$ 为键的可持久化计数线段树。截出高度范围后，只需对两个祖先版本做一次前缀计数。这里不需要二维数据结构：高度已经先被转化成了路径边界。

因此，$I(C,P_z)$ 可以在 $O(\log n)$ 时间内求出；任意祖先链是两条根路径之差，$I(C,Q)$ 同样是 $O(\log n)$。块内前缀查询及任意两段祖先链查询，也就都是 $O(\log n)$。

最后汇总复杂度。类型编号、倍增与可持久化线段树需要 $O(n\log n)$ 预处理时间、空间；所有块的分叉点表只需要 $O(n)$ 时间、空间。一次跨臂查询涉及 $O(\log n)$ 个高度层，每层至多五个块，每块花费 $O(\log n)$，故为 $O(\log^2 n)$。

边界 $q,q_0$ 也不会成为新的瓶颈：排名查询是 $O(\log n)$，即使直接用倍增配合排名判断寻找 $q_0$，也只有 $O(\log^2 n)$。其余三类询问分别固定两个端点、固定根、固定目标，使用排名公式和路径上的单调性即可在 $O(\log^2 n)$ 内完成。

最终得到 $O(n\log n+m\log^2 n)$ 时间、$O(n\log n)$ 空间的确定性在线算法。附带实现已进行本地样例检查、随机对拍，以及长链、星形树和多分叉长链的压力测试，尚未在 QOJ 提交。

这次的关键不是把任意路径逆序对做成 polylog，而是没有丢掉原题的条件：未饱和目标必定位于宽度与自身高度成正比的排名窗口中；这个窗口，在每个高度尺度上只穿过常数个块。