「有趣的笛卡尔树+倍增」LGP5654 基础函数练习题

· · 题解

sto 兔，尝试解释的更详细一点。

大概是比较神的题？首先如果考虑是 F(1,n)，那么转移就是一个笛卡尔树的形式。然后如果放到区间里来，可以发现可能会存在从 l、r 到根的链被修改，中间的链不会被改变。

而这个被修改成的模样大概是要稍微找一下性质。可以发现对于 l 而言，首先他的左子树会被砍掉，其次考虑对笛卡尔树的父子关系分类，称 {\rm Lson}(x)=y 的父子关系 (y,x) ，其中 x 是 y 的右行父亲，{\rm Rson}(x)=y 的则为左行父亲。那么不难看出，对于 l\to root 这条链上，任何一个键值(下标)比 l 小的都需要被删掉，也就是所有右行父亲都要被删掉；同理对于 r\to root 这条脸上，所有左行父亲需要被删掉。

发现询问可以离线，于是考虑拆成两半做。这个地方需要一个神奇的 Observation。观察 F 在笛卡尔树上的展开式：

\begin{aligned} F(l, r)& = \max\{F(l, m - 1), F(m + 1, r)\} + w_m \\ &= \max\{\max \{~F(l, m_1), F(m_1+1,m - 1)~\} + w_{m_1}, \max \{~F(m+1, m_2), F(m_2+1,r)~\} +w_{m_2} \} + w_m\\ & \cdots \end{aligned}

不难发现 m_k 只会与对应节点有关，同时 \max 有结合律，整个式子都被 \max 包住了，于是就可以直接倍增。

具体的，考虑设 g_{x,k} 表示 x 的 2^{k-1} 祖先的内向子树的贡献和，f_{x,k} 表示从 x 到 x 的 2^{k-1} 祖先的点权和，fa_{x,k} 表示对一个固定的方向，即不考虑「左行」或者「右行」父亲时的父亲。那么预处理时 f_{x,k} 较容易维护，考虑 g_{x,k} ，发现倍增是需要考虑分成两个 2^{k-1} 规模的子问题去计算，也就是此时需要分别计算 2^{k-1} 级祖先上面的和下面的贡献，拼一下的话比较直观。

然后就可以考虑如何计算答案。发现由于上文提到过的结合律，可以发现只需要比较链上的答案和子树内的答案的 \max 就好了。