吉司机线段树_成型笔记
JueFan 一只绝帆

吉司机线段树

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

HDU5306. Gorgeous Sequence

用例题引入吧。

给出序列,支持区间取 min⁡\min,区间和,区间 max⁡\max。

n≤106n\le 10^6。

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

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

若 x≥mx\ge m,则直接退出。

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

若 x≤sx\le s,则我们暴力递归。

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

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

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

代码。

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

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

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


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

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

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

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

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

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

P6242 【模板】线段树 3

给出一个长度为 nn 的数列 AA,同时定义一个辅助数组 BB,BB 开始与 AA 完全相同。接下来进行了 mm 次操作,操作有五种类型,按以下格式给出:

  • 1 l r k:对于所有的 i∈[l,r]i\in[l,r],将 AiA_i 加上 kk(kk 可以为负数)。
  • 2 l r v:对于所有的 i∈[l,r]i\in[l,r],将 AiA_i 变成 min⁡(Ai,v)\min(A_i,v)。
  • 3 l r:求 ∑i=lrAi\sum_{i=l}^{r}A_i。
  • 4 l r:对于所有的 i∈[l,r]i\in[l,r],求 AiA_i 的最大值。
  • 5 l r:对于所有的 i∈[l,r]i\in[l,r],求 BiB_i 的最大值。

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

n≤5×105n\le 5\times 10^5。

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

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

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

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

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

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

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

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

1
2
3
4
5
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∈[1,n]k\in[1,n] 求出只保留 ≤k\le k 的数,其笛卡尔树的子树大小和是多少。

n≤1.5×105n\le1.5\times 10^5。

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

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

正解其实是这样的:设向前找第一个比它大的位置是 pip_i,向后找第一个比它大的位置是 sis_i,那么中间一定是 ii 来管辖,即 sizi=si−pi−1siz_i=s_i-p_i-1。

所以我们可以拆贡献,每次求出 ∑si,∑pi\sum s_i,\sum p_i 即可。

我们从小往大插数,发现每次就是把它前面的人的 ss 和 ii 取 min⁡\min,把后面的人的 pp 和 ii 取 max⁡\max,然后因为是动态插数,后面的人的坐标都需要 +1+1。

区间加区间取 min⁡\min。

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

二重奏

维护两个序列 a,ba,b,支持对 aa 区间取 min⁡\min,对 bb 区间取 min⁡\min,对 aa 区间加,对 bb 区间加,询问 (ai+bi)max⁡(a_i+b_i)_{\max}。

n≤105n\le 10^5。

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

  • 为 aa 的最大值且为 bb 的最大值。
  • 为 aa 的最大值且不为 bb 的最大值。
  • 不为 aa 的最大值且为 bb 的最大值。
  • 不为 aa 的最大值且不为 bb 的最大值。

然后上吉司机即可。

[BZOJ5312]冒险

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

n,m≤105,V<231n,m\le 10^5,V<2^{31}。

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

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

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量