【学习笔记】吉司机线段树 |
您所在的位置：网站首页 › 线段树区间异或 › 【学习笔记】吉司机线段树 |
|
本文同步在CSDN上进行发表。 这是一篇刚开始学习线段树的小白都能看懂的良心学习笔记！ 前置知识：含有懒标记的线段树（没别的了）。 总述什么是吉司机线段树？ 就是维护区间最值和区间历史最值的线段树，它的名字来源于吉如一老师，他在 $2016$ 年发表了一篇集训队论文。 不过为啥这位老师被称为吉司机我也不知道…… 废话不多说，马上进入正题吧。 正题例题：Luogu 6242 读完题我们发现，一般线段树题目只需要用到一个数组，而这道题用了两个，多出来了个 $B$ 数组，是不是要拆成两棵树？ 通过分析已知的所有关于 $B$ 数组的条件，我们找出的答案是不用！ $B$ 数组最初和 $A$ 数组完全相同 每次操作后，将 $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 > 1; build(p |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |