笛卡尔树
笛卡尔树，是对 nnn 个键值对 (k,w)(k,w)(k,w) 建出的一种特殊的树。具体地，在这棵树里，kkk 值满足二叉搜索树的性质（左儿子小于根小于右儿子），www 满足堆的性质。在一般题目中，我们将序列下标设为 kkk，序列值设为 www。
图片
笛卡尔树的性质，就是二叉搜索树的性质加上堆的性质。
构建
假设我们的堆是小根堆。我们考虑按照 kkk 从小到大构建（也就是从左往右构建），显然对于第 iii 个，它一定是目前键最大的，因此它一定是在最右边的。那么，它就肯定不会出现在某个节点的左子树上（因为根据二叉搜索树性质，点的左子树都在点左侧）。于是，我们考虑维护笛卡尔树的右链。对于 iii，我们先将它假设为右链底端的点 ttt 的右儿子，然后只要 ai<ata_i<a_tai <at ，就一步步上浮，最终上浮到不能再上浮。此时，iii 下面那个点就是 iii 的左儿子，iii 上面那个点的右儿子就是 iii。我们发现，一个点被上浮过，就再也不在右链上了，因此可以使用单调栈维护。时间复杂度是
O(n)O(n)O(n)。
伪代码：
例题
P5854 【模板】笛卡尔树
板子题，不讲了。
Code:
P1377 [TJOI2011] 树的序
先手玩一下样例，容易发现其实答案就是搜索树的前序遍历，证明也很显然。所以这个题的复杂度瓶颈在于求搜索树，可以考虑使用笛卡尔树。题目描述里的键值 kkk 对应到笛卡尔树板子里应该是下标，所以我们令 aki=ia_{k_i}=iaki =i，然后对 aaa 数组建笛卡尔树即可。
Code:
LARGEST RECTANGLE IN A HISTOGRAM
考虑对于一个区间 [l,r][l,r][l,r] 的答案，容易发现，如果设其最小值为 mmm，答案是 m(r−l+1)m(r-l+1)m(r−l+1)。把这个直方图拍到笛卡尔树上，相当于对于一个点 uuu，它子树内有 sizusiz_usizu 个点，那么这个 uuu 的贡献是 sizuhusiz_uh_usizu hu ，因为笛卡尔树的性质保证了 huh_uhu 是整个子树内的最小值，所以这样是对的。
Code:
CF1220F GARDENER ALEX
首先我们考虑对于每一种排列的笛卡尔树是什么样的。它的根一定是 am=1a_m=1am =1 的 iii。如果我们令 b=[am+1,am+2,…,an,a1,a2,…,am−1]b=\left[a_{m+1},a_{m+2},\dots,a_n,a_1,a_2,\dots,a_{m-1}\right]b=[am+1 ,am+2 ,…,an ,a1 ,a2 ,…,am−1 ]，那么 mmm 的左子树就是 bbb 的一段后缀，右子树是 bbb 的一段前缀。设左子树最大深度为 d1d_1d1 ，右子树为 d2d_2d2 ，答案就是 max(d1,d2)+1\max(d_1,d_2)+1max(d1
,d2 )+1。
容易发现后缀其实是和前缀求法一样的，因此我们先只考虑前缀怎么做，再复制一遍就是后缀求法了。
可以设 depudep_udepu 表示点 uuu 的深度，maxdumaxd_umaxdu 表示 uuu 子树内最大的深度。考虑笛卡尔树构建过程中的每一个操作会对这些值产生什么影响。当我们 pop 一个元素 TTT 时，相当于将其下沉一格，也就是 depT←depT+1,maxdT←maxdT+1dep_{T}\gets dep_{T}+1,maxd_{T}\gets maxd_{T}+1depT ←depT +1,maxdT ←maxdT +1。当 TTT 的右儿子设为 iii 的时候，我们可以求出 depi=depT+1dep_i=dep_{T}+1depi =depT +1。如果
iii 上浮到根，则 depi=1dep_i=1depi =1。同时我们可以知道 maxdi=depimaxd_i=dep_imaxdi =depi 。当 iii 的左儿子设为 TTT 的时候，我们就可以更新 maxdmaxdmaxd 了。也就是 chkmax(maxd,maxx)chkmax(maxd,maxx)chkmax(maxd,maxx)，其中 maxxmaxxmaxx 是前面 pop 掉的所有元素里的最大 maxdmaxdmaxd 值。进行完这些操作之后，我们发现可以利用 maxdimaxd_imaxdi 去更新它的父亲的 maxdmaxdmaxd 了。前缀最大深度
preipre_iprei 一开始等于 prei−1pre_{i-1}prei−1 ，后面每更新一次 maxdmaxdmaxd，也要同时更新一下 preipre_iprei 。
然后最后求左移次数，假设 prei+sufi+1=anspre_i+suf_{i+1}=ansprei +sufi+1 =ans，那么说明 ama_mam 右侧有 iii 个点，因此左移次数为 (i+m) mod n(i+m)\bmod n(i+m)modn。
Code:
P6453 [COCI 2008/2009 #4] PERIODNI
观察题目给的图片，发现中间断开导致的合法情况，其实相当于在笛卡尔树中处于两个不同子树内。考虑树形 DP。
首先我们设 au=hu−hfaua_u=h_u-h_{fa_u}au =hu −hfau 。令 fu,if_{u,i}fu,i 表示在 uuu 的子树内放置 iii 个方案数，gu,ig_{u,i}gu,i 表示在 uuu 子树内（不包括 uuu）放 iii 个的方案数。
然后我们发现，儿子与父亲其实是有下面一部分重叠的部分的（大小为 hfah_{fa}hfa ），非常不好处理，所以我们定义点 uuu 上，能放置的位置只有 aua_uau 个，而不是 huh_uhu 。
考虑转移，fu,if_{u,i}fu,i 可以先在儿子上放 i−ji-ji−j 个，再在下面一大堆重叠部分放 jjj 个。下面重叠的是一个矩形形状。如果笛卡尔树上点 uuu 管辖区间是 [lu,ru][l_u,r_u][lu ,ru ]，那么这个矩形的长宽就分别是：ru−lu+1,aur_u-l_u+1,a_uru −lu +1,au 。但是，由于我们需要在儿子上放置 i−ji-ji−j 个，所以矩形有 i−ji-ji−j 列不能放了，所以实际的长宽是 ru−lu+1−(i−j),aur_u-l_u+1-(i-j),a_uru −lu +1−(i−j),au 。我们需要在这个矩形里放 jjj
个且没有同行同列。首先我们选择 jjj 列，方案数 (ru−lu+1−(i−j)j)\binom{r_u-l_u+1-(i-j)}{j}(jru −lu +1−(i−j) )；然后我们选择 jjj 行，方案数 (auj)\binom{a_u}{j}(jau )。这样我们就确定了 jjj 个点。但是呢，这 jjj 个点的行列换一下位置，其实是不同的方案，所以要再乘一个 j!j!j!。
gu,ig_{u,i}gu,i 是比较简单的，应该是 ∑flsu,jfrsu,i−j\sum f_{ls_u,j}f_{rs_u,i-j}∑flsu ,j frsu ,i−j 。
总转移就长这样：
gu,i=∑j=0iflsu,jfrsu,i−jfu,i=∑j=0igu,i−j(ru−lu+1−i+jj)(auj)j!g_{u,i}=\sum_{j=0}^i f_{ls_u,j}f_{rs_u,i-j} \\ f_{u,i}=\sum_{j=0}^i g_{u,i-j}\binom{r_u-l_u+1-i+j}{j}\binom{a_u}{j}j! gu,i =j=0∑i flsu ,j frsu ,i−j fu,i =j=0∑i gu,i−j (jru −lu +1−i+j )(jau )j!
边界比较简单：
fu,0=1fu,1=augu,0=1f0,0=1f_{u,0}=1 \\ f_{u,1}=a_u \\ g_{u,0}=1 \\ f_{0,0}=1 fu,0 =1fu,1 =au gu,0 =1f0,0 =1
时间复杂度：O(n3)O(n^3)O(n3)。
Code:
P5654 基础函数练习题
首先这个 F(l,r)F(l,r)F(l,r) 其实就是对于区间 [l,r][l,r][l,r] 建立大根笛卡尔树，然后查询从 LCA(l,r)\operatorname{LCA}(l,r)LCA(l,r) 向下走，到一个儿子数量 <2<2<2 的点的最大点权和。
设 t=LCA(l,r)t=\operatorname{LCA}(l,r)t=LCA(l,r)，则有：
F(l,r)=max(F(l,t−1),F(t+1,r))+wtF(l,r)=\max\left(F(l,t-1),F(t+1,r)\right)+w_t F(l,r)=max(F(l,t−1),F(t+1,r))+wt
考虑把两边分别算出来，这样 l,rl,rl,r 的两个限制就会变成一个限制。容易发现第二项和第一项是对称的，所以我们只考虑怎么算 F(l,t−1)F(l,t-1)F(l,t−1)。
显然所有的答案都是发生在 ≥l\geq l≥l 的位置的，所以我们从 lll 开始向上跳（只往右跳），这样肯定覆盖所有答案。至于为什么只往右跳，考虑笛卡尔树性质可以得知，uuu 的右子树所有点一定 >u>u>u，而 lll 的祖先的子树肯定有 lll 这个点，因此如果 uuu 在 lll 的左侧，那 u<lu<lu<l 是必然的。
那么既然向左的父亲没用，我们不妨直接扔掉吧。设 uuu 的右儿子是 rsrsrs，则定义 fars=faufa_{rs}=fa_ufars =fau 即可。
重定义父亲后就可以正常让 lll 向上跳了。考虑 lll 点的答案怎么算。首先，lll 的右子树肯定是可以参与计算的（都 >l>l>l，提前预处理即可），然后再求一个 dist(l,t)dist(l,t)dist(l,t) 加进去就行。这个暴力做是 O(n)O(n)O(n) 的。
我们直接考虑倍增，令 fau,ifa_{u,i}fau,i 表示 uuu 向上走 2i2^i2i 步的点（当然，是重定义之后的父亲），juu,iju_{u,i}juu,i 表示从 uuu 向上走 2i−12^i-12i−1 步经过的点权和，resu,ires_{u,i}resu,i 表示当 l=u,t=fau,il=u,t=fa_{u,i}l=u,t=fau,i 时的答案。
转移如下：
fau,i=fafau,i−1,i−1juu,i=juu,i−1+jufau,i−1,i−1resu,i=max(resfau,i−1,i−1,resu,i−1+jufau,i−1,i−1)fa_{u,i}=fa_{fa_{u,i-1},i-1} \\ ju_{u,i}=ju_{u,i-1}+ju_{fa_{u,i-1},i-1} \\ res_{u,i}=\max(res_{fa_{u,i-1},i-1},res_{u,i-1}+ju_{fa_{u,i-1},i-1}) fau,i =fafau,i−1 ,i−1 juu,i =juu,i−1 +jufau,i−1 ,i−1 resu,i
=max(resfau,i−1 ,i−1 ,resu,i−1 +jufau,i−1 ,i−1 )
当处理 F(t+1,r)F(t+1,r)F(t+1,r) 的时候，只需要再次重定义 fafafa 即可。
然后我们注意到老牧师出题人只给开 250 MB 大小，哦不不不我无疑是愤怒的，所以要节约一些数组，把倍增数组循环利用一下。显然离线询问下来把两边分别放一块算就能节约一半。
时间复杂度：O(nlogn)O(n \log n)O(nlogn)。
Code:
