【学习笔记】吉司机线段树

Mysterious_Mini · 2021-08-10 17:17:57 · 题解

本文同步在CSDN上进行发表。

这是一篇刚开始学习线段树的小白都能看懂的良心学习笔记！

前置知识：含有懒标记的线段树（没别的了）。

总述

什么是吉司机线段树？

就是维护区间最值和区间历史最值的线段树，它的名字来源于吉如一老师，他在 2016 年发表了一篇集训队论文。

不过为啥这位老师被称为吉司机我也不知道……

废话不多说，马上进入正题吧。

正题

例题：Luogu 6242

读完题我们发现，一般线段树题目只需要用到一个数组，而这道题用了两个，多出来了个 B 数组，是不是要拆成两棵树？

通过分析已知的所有关于 B 数组的条件，我们找出的答案是不用！

每次操作后，将 B 数组更新，使 B_i = \max(B_i,A_i)

这里我给出了两个条件，条件 1 是 B 数组的初始化，条件 2 是 B 数组的更新。显然可得：B_i 是出现过的所有 A_i 的最大值。

得出结论：B 数组维护 A 数组的历史最大值，两者公用一棵线段树。

题干分析完之后，让我们来分析一下操作。

操作号	简述
1	区间加法
2	区间修改为最小值
3	区间求和
4	区间查询最大值
5	区间查询历史最大值中的最大值

接下来，我会分模块讲解（一定要往下看哟，有代码 /se）。

吉司机线段树本质上就是带懒标记的线段树，所以代码和线段树的前两个模板题也是大同小异的。

都有啥？

struct SegTree {};
void pushup()
void build()
void pushdown()
void modify()
// 此处省略N个modify……
int query()
// 此处省略N个query……

看着就码量惊人，所以我们要在保证代码可读性的基础上尝试减少码量，原因有二：

代码相对短，看着舒服（要不然会感觉像在写大 % 你）
由于这题代码不可避免的长（函数多，维护操作多），所以出错的概率也会比较高，错了之后调代码会令人崩溃。为了自己的心理健康着想，还是要把代码写的漂亮一点的。

具体怎样减少码量，我会在后文进行详细的描述。

线段树结构体

struct SegTree
{
    int sum, maxst, maxnd, maxhis, maxnum, l, r;
    int lazy1, lazy2, lazy3, lazy4;
    void clear() { lazy1 = lazy2 = lazy3 = lazy4 = 0; }
} tree[NR << 2];

注：

为了方便，接下来我会把严格次大值称为次大值，但是读者勿忘它的真实含义！
我后文会将 sum，maxst，maxnd，maxnum 称为四大天王（还是想偷懒）。

我们运用一些 #define 来减少码量。

#define sum(p) tree[p].sum
#define max1(p) tree[p].maxst
#define max2(p) tree[p].maxnd
#define maxhis(p) tree[p].maxhis
#define cnt(p) tree[p].maxnum
#define l(p) tree[p].l
#define r(p) tree[p].r
#define lzy1(p) tree[p].lazy1
#define lzy2(p) tree[p].lazy2
#define lzy3(p) tree[p].lazy3
#define lzy4(p) tree[p].lazy4

看着感觉像在增加码量，不过我保证，最终码量一定会减少的qwq！

我试了试，加了这坨 #define 总码量 3.54KB，不加 3.95KB。

建树

递归的过程中，记录区间左右端点。

如果递归到了叶子结点（即 l = r），初始化四大天王和区间最大值的个数。由于区间里只有 1 个元素 A_l，所以把区间最大值出现的次数设为 1。四大天王中除了区间次大值，都初始化为 A_l。由于没有第二个数了，就暂且将区间次大值初始化为 \text{-INF}，这样是个数就能比它大，方便更新（如果初始化的不够小，比 A 数组的最小值 -5 \times 10^8 大，就会造成无法更新的局面，一定要注意）。

void build(int p, int l, int r)
{
    l(p) = l, r(p) = r;
    if(l == r) { sum(p) = max1(p) = maxhis(p) = a[l], max2(p) = -INF, cnt(p) = 1; return; }
    int mid = (l + r) >> 1; build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r), pushup(p);
}

向上更新

pushup() 会更新四大天王及区间最大值的出现次数。

区间最大值肯定是两个子区间最大元素中大的那一个，区间历史最大值同理。

区间和是两个子区间的和相加的结果。

对于区间最大值的出现次数：

当左子区间最大元素和右子区间最大元素相等时，它们父区间的最大元素出现次数就是两个子区间相加的结果。
否则，它们父区间的最大元素出现次数等于左右两个子区间中区间最大值大的那个区间的最大元素出现次数。

对于区间次大值：

当左子区间最大元素和右子区间最大元素相等时，它们父区间的次大元素等于两个子区间次大元素中大的那一个。
否则，它们父区间的次大元素等于最大元素小的那个子区间的最大元素和另一个子区间的次大元素中的最大值。

void pushup(int p)
{
    max1(p) = max(max1(p << 1), max1(p << 1 | 1));
    maxhis(p) = max(maxhis(p << 1), maxhis(p << 1 | 1));
    sum(p) = sum(p << 1) + sum(p << 1 | 1);
    if(max1(p << 1) == max1(p << 1 | 1)) max2(p) = max(max2(p << 1), max2(p << 1 | 1)), cnt(p) = cnt(p << 1) + cnt(p << 1 | 1);
    if(max1(p << 1) > max1(p << 1 | 1)) max2(p) = max(max1(p << 1 | 1), max2(p << 1)), cnt(p) = cnt(p << 1);
    if(max1(p << 1) < max1(p << 1 | 1)) max2(p) = max(max1(p << 1), max2(p << 1 | 1)), cnt(p) = cnt(p << 1 | 1);
}

下传懒标记

由于这道题维护了 4 个懒标记，下传懒标记时会比较复杂，为了方便理解，我们把下传懒标记的操作拆成 2 个函数：update() 和 pushdown()（其实要论关系，update() 其实是 pushdown() 的子函数）。

先来看看 update()。

更新区间和：把区间里的最大值个数乘上 l1，其它数的个数乘上 l3，它们的和就是区间和新增的部分。

更新区间次大值：如果区间不同值个数并非一，那么加上 l3（如果不同值个数为一，则不存在次大值，即次大值为 \text{-INF}）。

接下来是 4 个懒标记的更新，注意更新的顺序！

其余变量和代码一起理解，也就不是那么难了。

void update(int p, int l1, int l2, int l3, int l4)
{
    sum(p) += (l1 * cnt(p) + l3 * (rson(p) - lson(p) + 1 - cnt(p)));
    maxhis(p) = max(maxhis(p), max1(p) + l2);
    max1(p) += l1;
    if(max2(p) != -INF) max2(p) += l3;
    lzy2(p) = max(lzy2(p), lzy1(p) + l2), lzy1(p) += l1;
    lzy4(p) = max(lzy4(p), lzy3(p) + l4), lzy3(p) += l3;
}

下面该讲 pushdown() 了：

对于这题的 pushdown()，我们需要分两种情况讨论。

众所周知，一个区间可以拆成两个子区间（左右儿子），对于一个子区间，如果其包含的最大元素比另一子区间包含的最大元素大，那么父区间要以更新最大值的礼仪来接待它，否则就按照更新非最大值的礼仪来接待它。

详见代码，注意懒标记用过之后要清零。

void pushdown(int p)
{
    int maxn = max(max1(p << 1), max1(p << 1 | 1));
    if(max1(p << 1) == maxn) update(p << 1, lzy1(p), lzy2(p), lzy3(p), lzy4(p));
    else update(p << 1, lzy3(p), lzy4(p), lzy3(p), lzy4(p));
    if(max1(p << 1 | 1) == maxn) update(p << 1 | 1, lzy1(p), lzy2(p), lzy3(p), lzy4(p));
    else update(p << 1 | 1, lzy3(p), lzy4(p), lzy3(p), lzy4(p));
    tree[p].clear();
}

坑点：maxn 要在函数最开始记录！不能每次在判断时比较两个子区间包含的最大元素大小！ 我因为这个，一直 Unaccepted 了一个月，花了两个晚上去食堂吃饭的时间，还因此瘦了 2 斤 /kk

操作 1

正常 modify() 操作，如果区间在待更新的范围内，那么把所有数都加上 k ，即 update(p, k, k, k, k)。

void modify1(int p)
{
    if(l(p) > y || r(p) < x) return;
    if(l(p) >= x && r(p) <= y) { update(p, k, k, k, k); return; }
    pushdown(p), modify1(p << 1), modify1(p << 1 | 1), pushup(p);
}

操作 2

在操作 1 的基础上有一些修改。

如果区间最大值都比 k 小，那么无需更新，直接 return。

如果合法，还要进一步分类讨论：

如果 max2 \le k \le max1，则只需要更新 max1，把 update() 中的 l1 和 l2 都设置为 k - max1(p)（因为 update() 是加法操作，所以加上相反数等于减去该数，最终就能达到更新为 k 的效果了）。
否则，还需要向下推进，直到符合上面的那种情况才停止。

void modify2(int p)
{
    if(l(p) > y || r(p) < x || max1(p) <= k) return;
    if(l(p) >= x && r(p) <= y && max2(p) < k) { update(p, k - max1(p), k - max1(p), 0, 0); return; }
    pushdown(p), modify2(p << 1), modify2(p << 1 | 1), pushup(p);
}

询问操作

很常规，就不放代码了。

这里说几个其中的坑点：

求最大值时判断非法情况一定要返回极小值！
求和操作的非法情况返回 0。

后记

这题要用 long long，给出简单证明：

因为 1 \le n,m \le 5 \times 10^5，-5 \times 10^8 \le A_i \le 5 \times 10^8，所以如果操作 3 中的 l=1,r=n，那么结果的取值范围是 -2.5 \times 10^{14} \le ans \le 2.5 \times 10 ^ {14}，显然需要用到长整型。

但是细心的读者可能会看出我的所有代码都只有 int 的身影，这是因为我太懒，直接 #define int long long 了。大家写代码可不要被迷惑了哦！

其实，这篇文章可能不会在这个时间出现……

一个月里，Mini 的 P6242 代码一直卡在 40 分。直到有一天，他闲来无事，来到了快要放弃的这题，点开了提交记录。

忽然，他看到了挨的很近的两条提交记录，作者是同一个人，一次是 40 分，另一次是 100 分。

他有些好奇，点开了 40 分的那条提交记录，把光标放在了 WA 的 6 个测试点上。忽然，他惊喜地发现，这个提交记录每个测试点首次错误的的位置都和他的废弃代码一模一样。

于是，他连忙给这两份提交记录的作者发了私信，问了他这道题应该怎么修改。很快，对方就给出了回复：

您的 pushdown() 函数有问题。

并一针见血的指出了问题所在。

Mini 将这个问题改完之后，马上 AC 了！

在此，我由衷感谢这位乐于助人的大佬 @zhimao ！

希望我的文章能够帮到大家！

如果您觉得这篇文章对您有帮助，可以给个赞嘛 qwq