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

皎月半洒花

2020-06-16 21:28:58

Solution

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$ 就好了。