区间笛卡尔树

题意：有序列 $a_i,b_i$，对区间 $a_i$ 建出笛卡尔树，点 $u$ 有 $f_u=b_u-f_{ls_u}+f_{rs_u}$，求根的答案。

首先我们对整个序列建出笛卡尔树并处理出 $f_u$。先考虑右儿子怎么做，可以发现就是单调栈上的一个后缀 $b_u-f_{ls_u}$ 加起来，做一个前缀和就行。

左儿子也是类似，但是每个点的贡献要乘上 $(-1)^{dep_u}$。我们先将在单调栈上的位置的奇偶性当作深度的奇偶性，询问的时候分讨一下 $p_0$ 位置的奇偶性。

通常为了方便，第一步的区间 RMQ 可以直接在单调栈上二分。本题使用线性 RMQ 即可做到线性，但通常没有什么必要。

题意：有序列 $a_i$，每次询问 $\min\limits_{i\in[l,r]}\sum\limits_{j\in[l,r]}\max\limits_{k\in[\min(i,j),\max(i,j)]}a_k$。

我们先在笛卡尔树上写出 DP：$f_u=\min(f_{ls_u}+a_u(sz_{rs_u}+1),f_{rs_u}+a_u(sz_{ls_u}+1))$。

两边是对称的，我们就只考虑左边。我们考虑最小的 $i$ 使得 $p_i$ 采用了第二种转移，即 $f_{p_i}=f_{rs}+a_{p_i}(p_i-l+1)$，那 $f_{p_1}=f_{p_i}+\sum\limits_{1\le j<i}a_{p_j}(sz_{rs_{p_j}}+1)$，答案就是所有 $p_i$ 的结果的最小值。在单调栈上前缀和然后拆贡献，KTT 维护一次函数最值。$\mathcal O(n\log^2n)$。

题意：有一个网格，一个单元格 $(x,y)$ 合法当且仅当 $a_x>b_y$，问保留第 $[l,r]$ 列，$(0,x)$ 能不能走到 $(0,y)$。

我们猜测路径一定形如一堆 $(0,a)\to(x,a)\to(x,b)\to(0,b)$。设一列中第一个空的位置是 $fi_i$，前缀连续空的长度是 $cn_i$，$a\to b$ 之间的 $\max b$ 位置为 $c$，那能这么走就相当于 $fi_c\le\min(cn_a,cn_b)$。

我们建出 $b$ 的笛卡尔树。对于一个子树 $x$，如果我们能到达 $fi_x$ 且子树 $\max cn\ge fi_{fa_x}$ 就可以走到 $fi_{fa_x}$，询问的时候只要看能跳到最高的位置是否相等。

考虑区间笛卡尔树，所有前缀 $\max$ 相当于不停跳到右侧第一个 $>b_i$ 的位置，这个也能建出一棵树，在全局的笛卡尔树上倍增到子树不被 $[l+1,r-1]$ 包含后变成在这棵树上倍增即可。$O(n\log n)$。