一类区间笛卡尔树问题的套路

某些题目要求我们对于区间建出笛卡尔树后进行关于笛卡尔树的询问，这里介绍其中一类询问的套路。

CF1117G

题意：建出区间笛卡尔树后求出子树大小之和。

子树大小可以是 \(r_i-l_i+1\)（\([l_i,r_i]\) 代表节点 \(i\) 子树代表的区间），从这里进行考虑。

我们考虑建立笛卡尔树的过程。我们开了一个栈，然后插入节点的过程就是踢掉一堆节点再加入一个节点。

这个操作可以认为是 固定踢掉节点的左右端点，并令还在栈内的节点右移右端点。

考虑一个区间的笛卡尔树扩展到整个序列的情况。可以先加入右边的节点再加入左边的节点。

发现上述过程仍然正确。

因此对于这一类问题，如果每一个节点对答案的贡献只和左右端点以及下标有关，我们可以直接对序列建出笛卡尔树，获取 \([l_i,r_i]\) 后取其对询问区间 \([L,R]\) 的交集。

又注意到，这个操作的本质是 对整个序列的笛卡尔树建立虚树，所以操作显然是正确的。

对于这个题目，我们要求的就是 \(\sum_{i=L}^R\max(r_i,R)-\min(l_i,L)+1\)，可以将 \(\max\) 和 \(\min\) 拆开后使用树状数组分别维护。复杂度 \(O(n\log n)\)。

LGP3246

题意：求 \(\sum_{l=L}^R\sum_{r=l}^R\min([l,r])\)。

化简问题，变为 \(\sum_{i=L}^R a_i(\min(r_i,R)-i+1)(i-\max(l_i,L)+1)\)。

\[\sum_{i=L}^R V_i(\min(r_i+1,R+1)-i)(i-\max(l_i-1,L-1)) \]

\[(\sum_{i=L}^R i\times V_i(\min(r_i+1,R+1)+\max(l_i-1,L-1)))-(\sum_{i=L}^RV_i\min(r_i+1,R+1)\max(l_i-1,L-1))-(\sum_{i=L}^Ri^2\times V_i) \]

拆成三类贡献后，问题相当于二维带权数点，树套树维护即可 \(O(n\log^2n)\)。

然而？

仔细观察一下。第一个 \(\sum\) 和第三个 \(\sum\) 相当好处理，只需要考虑第二个 \(\sum\)。

考虑四类区间的贡献：被询问区间包含，包含询问区间，只有左端点越出询问区间和只有右端点越出循环区间。

考虑序列上不在询问区间中的区间。发现这一类区间一定是三类贡献或四类贡献。

于是我们可以考虑对整个序列询问这个，然后对前缀和后缀单独询问，贡献是形如 \(\sum_{i=1}^{L-1}V_i(L-1)\min(r_i+1,R+1)\)，可以使用树状数组解决。

接下来只需要思考解决 \(\sum_{i=1}^nV_i\min(r_i+1,R+1)\max(l_i-1,L-1)\)。这一类问题是静态二维带权数点，主席树即可 \(O(n\log n)\)。

使用前缀和稍微优化即可做到每次询问只需要一次主席树查询。

LGP5654

题意：每次对询问区间建立笛卡尔树，请找到一个点使得其到根节点的距离最大。

容易设计一个 DP：\(dp[u]=\max(dp[ls[u]],dp[rs[u]])+a[u]\)。

这个套路的意思是，我们可以找出区间笛卡尔树每个节点代表哪些区间。

我们将节点分为四类：区间在询问区间中，只有左端点在询问区间外和只有右端点在询问区间外。

在注意到，第二类节点和第三类节点，对应的正好是 后缀笛卡尔树的左链 和 前缀笛卡尔树的右链。（前面两道题也可以这样分类）

所以，我们可以将询问离线到左右端点，然后每次在栈上查询信息就行了。

注意到二类和三类，甚至四类都是栈的一个后缀（即栈顶的一些元素），所以我们可以维护一个当前节点到最远孙子的距离，然后在出栈时将信息合并到父亲上。

对于栈内元素，将该节点到目前根节点的距离加上 \(dp\) 值丢入线段树，查询时查询后缀最大值即可。

复杂度 \(O(n\log n)\)。

以上均为口胡，如有错误博主概不负责