吉司机线段树

需要注意，如果仅仅是区间取 $\max$ ，区间取 $\min$ ，区间求 $\max$ ，区间求 $\min$ ，区间加，这是可以单 $\log$ 的，只有求区间和这种阴间东西的时候才需要 beats，带上区间加就 $\log^2$ 。

HDU5306. Gorgeous Sequence

用例题引入吧。

给出序列，支持区间取 $\min$ ，区间和，区间 $\max$ 。

$n\le 10^6$ 。

维护区间 $\max$ ，严格次大 $\max$ ，区间和，区间 $\max$ 个数，设为 $(m,s,a,c)$ ，没有 $s$ 则 $s$ 默认是 $-\infty$ 。

我们用这前两个信息尽可能剪枝。

若 $x\ge m$ ，则直接退出。

若 $x\in(s,m)$ ，则等价于所有 $m$ 变成 $x$ ，对 $c$ 的贡献显然没有，对 $a$ 的贡献利用 $c$ 计算即可，可以直接修改这个节点的信息，但记得打上一个修改标记。

若 $x\le s$ ，则我们暴力递归。

我们尝试证明这个东西是对的，定义势能函数是所有节点的数的种类数的和，最初这个值是 $\Theta(n\log n)$ 的。

若每次需要往两边递归，则我们必定合并 $s,m$ ，种类数减少 $1$ 。

所以维护此类问题的最常见方法就是取 $\min$ 维护 $\max,s\max$ ，取 $\max$ 维护 $\min,s\min$ 。

代码。

唯一需要注意的点就是要注意这仍然是个需要 down 的线段树，不要以为啥都没有。

若加上区间加，则代码基本没变化，只需要改改标记就好，理论表现是 $\Theta(n\log^2 n)$ ，均摊易证。

维护 $(m,s,a,c)$ 和 $(a,e)$ （先加上了 $a$ ，又对 $e$ 取了 $\min$ ），由于只要我们打上了标记，我们一定是只对 $m$ 这一种数进行各种操作，这是吉司机线段树的核心思想，所以我们可以轻易的合并标记 $(a_1,e_1)\cdot(a_2,e_2)=(a_1+a_2,\min(e_2,e_1+a_2))$ 。

先停停，我们来总结一下这类题目有什么通用的套路。

发现有一个区间取 $\min$ 操作，我们现在有一个很厉害的想法：维护两套信息。

即最大值和非最大值的信息都要维护，取 $\min$ 在这个想法中变成了一种另类的对最大值的“区间加”。

用这个思路重写一遍刚刚的题你会发现思路清晰了很多。

我们意识到，取 $\min$ 这个操作应该跟其他操作写成两种，显然二者的处理风格不一样。

这是之前写的，我花了很久研究这个东西如何写的结构化一点，然后发现这个写法麻烦又不实用，吉司机线段树维护的信息并没有很泛化，所以我们不会遇到复杂的问题，遇到了直接暴力写就好。

P6242 【模板】线段树 3

给出一个长度为 $n$ 的数列 $A$ ，同时定义一个辅助数组 $B$ ， $B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出：

1 l r k：对于所有的 $i\in[l,r]$ ，将 $A_i$ 加上 $k$ （ $k$ 可以为负数）。

2 l r v：对于所有的 $i\in[l,r]$ ，将 $A_i$ 变成 $\min(A_i,v)$ 。

3 l r：求 $\sum_{i=l}^{r}A_i$ 。

4 l r：对于所有的 $i\in[l,r]$ ，求 $A_i$ 的最大值。

5 l r：对于所有的 $i\in[l,r]$ ，求 $B_i$ 的最大值。

在每一次操作后，我们都进行一次更新，让 $B_i\gets\max(B_i,A_i)$ 。

$n\le 5\times 10^5$ 。

区间历史最值和这玩意套起来了。

由于吉司机线段树将取 $\min$ 变成了对一种数的操作，往往用区间赋值或区间加来理解更为妥当。

只不过这个“区间”是仅对最大值生效的。

序列信息显然需要多维护一个历史最大值变成 $(m,s,a,c,p)$ 。

然后我们想区间历史最值需要维护什么标记。

当我们取 $\min$ 时显然不会对区间历史最值产生贡献，但当我们区间减的时候，我们自然想要留住这个最大的加法 $\text{tag}$ 。

我们把标记扩充到 $(a_m,a_s,p_m,p_s)$ ，前两个表示对最大值和非最大值的加法标记，后两个表示前两个标记的历史最大值。

使用这个标记更新历史最大值无疑是简单的，而标记的下传需要一点门道。

inline void down(int L,int R,int d) {ll md=max(ma[l(d)],ma[r(d)]);
    pr(L,mid,l(d),ma[l(d)]==md?t1[d]:t2[d],t2[d],ma[l(d)]==md?t3[d]:t4[d],t4[d]),
    pr(mid+1,R,r(d),ma[r(d)]==md?t1[d]:t2[d],t2[d],ma[r(d)]==md?t3[d]:t4[d],t4[d]),
    t1[d]=t2[d]=t3[d]=t4[d]=0;
}

你并不能判断 ma[l(d)],ma[r(d)] 和 ma[d] 的关系，因为 ma[d] 已经是修改过的值了，我们只用 md 来判断标记的下传。

CF1290E Cartesian Tree

给定一个排列，对于 $k\in[1,n]$ 求出只保留 $\le k$ 的数，其笛卡尔树的子树大小和是多少。

$n\le1.5\times 10^5$ 。

*3300 评了个紫就知道大事不妙了。

想到一个套路 $\sum siz=\sum dep$ ，可惜没什么用。

正解其实是这样的：设向前找第一个比它大的位置是 $p_i$ ，向后找第一个比它大的位置是 $s_i$ ，那么中间一定是 $i$ 来管辖，即 $siz_i=s_i-p_i-1$ 。

所以我们可以拆贡献，每次求出 $\sum s_i,\sum p_i$ 即可。

我们从小往大插数，发现每次就是把它前面的人的 $s$ 和 $i$ 取 $\min$ ，把后面的人的 $p$ 和 $i$ 取 $\max$ ，然后因为是动态插数，后面的人的坐标都需要 $+1$ 。

区间加区间取 $\min$ 。

注意实际上我们是在插数，所以还没有插进去的部分默认值应该不影响任何东西，即 len=0,cn=0,mx=-inf,mn=inf,sum=0。

二重奏

维护两个序列 $a,b$ ，支持对 $a$ 区间取 $\min$ ，对 $b$ 区间取 $\min$ ，对 $a$ 区间加，对 $b$ 区间加，询问 $(a_i+b_i)_{\max}$ 。

$n\le 10^5$ 。

运用类似的思路，我们对每种数单独维护一套标记，具体来说我们维护这四种位置的标记：

为 $a$ 的最大值且为 $b$ 的最大值。
为 $a$ 的最大值且不为 $b$ 的最大值。
不为 $a$ 的最大值且为 $b$ 的最大值。
不为 $a$ 的最大值且不为 $b$ 的最大值。

然后上吉司机即可。

[BZOJ5312]冒险

维护一个长度为 n 的序列，支持 m 次操作，操作包括区间按位或一个数，区间按位与一个数，以及查询区间最大值。

$n,m\le 10^5,V<2^{31}$ 。

对 and 和对 or 的影响相同时候操作退化成区间加，仔细思考一下发现势能是对的。

这类题通常需要想怎么退化成区间加。