腾飞计划寒假第七课——线段树 2025/2/8
Lovely_yhb
·
·
个人记录
线段树进进进进进接
P6327 区间加区间 sin 和
和角公式，维护 \sin 值和 \cos 值。
P4198 楼房重建
维护一个序列。
- 单点修改。
- 查询全局有多少个位置是前缀最大值。
维护 maxx（区间最大值），ans（区间有多少个数是前缀最大值）。
设 f_{i,j} 表示 i 点被 j 高度遮挡后的答案。
1. 如果 $a_{maxx}>b_{maxx}$，$f_{b,a_{maxx}}=f_{d,a_{maxx}}$。
2. 否则如果 $a_{maxx}\le c_{maxx}$ 往下递归 $c$，$f_{b,a_{maxx}}=f_{c,a_{maxx}}+f_{d,c_{maxx}}$。但这样复杂度会爆，发现 $f_{d,c_{maxx}}=b_{ans}-c_{ans}$，只把 $c$ 往下递归即可。
合并是 $O(\log n)$ 的，线段树总体复杂度 $O(n\log^2 n)$。
### [Distinct Integers](https://www.luogu.com.cn/problem/AT_jsc2019_final_h)
$f_i$ 表示以 $i$ 为右端点，左端点最多跳到哪。
对前缀中的每一个 $i$ 找到 $pre_i$，$i$ 的前缀 $pre_i$ 的最大值就是 $f_i$。
查询的就是区间中每个 $i$，找到 $i-f_i$ 的和。
线段树每个区间上维护一个最大值和前缀最大值的和。
如果 $pre_i$ 在区间之外会有问题，因为从区间左端点到 $pre_i$ 会多算。
因为 $i$ 越大，$f_i$ 越大，所以可以二分一个边界，使这个边界左边的 $f$ 都越过了 $l$，右边的都没越过 $l$，左右单独算。
### [P9130 [USACO23FEB] Hungry Cow P](https://www.luogu.com.cn/problem/P9130)
把送干草转化成左括号，每一天转化成右括号，查有多少个右括号能匹配。每个右括号是有权值的（天的编号）。
线段树维护，目前没有匹配的右括号的和，左括号个数，右括号个数。
如果右边右括号小于等于左边左括号，右边可以合并完。
否则只会合并一部分，考虑这部分右括号的来源。
如果全在左区间就递归左区间，如果一部分在左区间一部分在右区间，左区间的部分直接加和就行，递归右区间。
### [CF280D k-Maximum Subsequence Sum](https://www.luogu.com.cn/problem/CF280D)
合理猜测复杂度 $O(nk\log n)$。
反悔贪心。先选上一个区间，如果它不优再把它扔掉，把选了的数把它标记为它的相反数，再选就相当于把它丢掉，这样选出的区间就可以相交了（聪明。
跑 $k$ 次，每次选出最大子段和，然后区间乘 $-1$，维护一下最大子段和的区间。
线段树维护：
1. 查询最大子段和。
2. 区间乘 $-1$。
发现标记状态很少，只有两种，可以维护打标记之前的信息和打标记之后的信息，即维护最大子段和和最小子段和，乘 $-1$ 之后将二者乘 $-1$ 再交换即可。
### [P2894 [USACO08FEB] Hotel G](https://www.luogu.com.cn/problem/P2894)
线段树上二分，区间修改。
维护以下信息：
1. 区间最大连续空房数。
2. 区间长度 。
3. 从左开始或从右开始的最大连续空房数。
非常简单。
### [CF620E New Year Tree](https://www.luogu.com.cn/problem/CF620E)
线段树每个节点记一个 bitset 表示每个颜色是否出现过。
子树操作线段树维护 dfs 序即可。
### [CF242E XOR on Segment](https://www.luogu.com.cn/problem/CF242E)
无脑拆位
维护一个 01 区间，区间异或，区间十进制求和。
维护 $\log$ 个线段树，每个线段树维护每一位。
### [P6492 [COCI 2010/2011 #6] STEP](https://www.luogu.com.cn/problem/P6492)
线段树维护答案区间的左右端点，前缀答案，后缀答案，区间答案，合并非常简单。
修改是区间。
### [CF718C Sasha and Array](https://www.luogu.com.cn/problem/CF718C)
线段树维护矩阵，每个点维护斐波那契数列递推矩阵的 $x_i$ 次方，区间维护矩阵和，修改时打上乘 $A^k$ 的标记即可。
### [P1438 无聊的数列](https://www.luogu.com.cn/problem/P1438)
查单点：差分数组上做。
查区间：区间懒标记打上首项和公差。
### [CF739C Alyona and towers](https://www.luogu.com.cn/problem/CF739C)
维护一个数组，$a_{i-1}$ 和 $a_i$ 的关系，如果小于就是 $0$，如果大于就是 $1$。每次修改时单点修改，查最长先 $0$后 $1$ 的段。
左边的后缀全 $0$ 段和右边的前缀先 $0$ 后 $1$ 段合并，左边的后缀先 $0$ 后 $1$ 段和右边的前缀全 $1$ 段合并。
也就是维护 $5$ 个信息：后缀全 $0$ 段、前缀先 $0$ 后 $1$ 段、后缀先 $0$ 后 $1$ 段、前缀全 $1$ 段、区间答案。
## 可持久化线段树
可持久化线段树是用动态开点线段树实现的。
每次修改/查询只有最多 $\log$ 个点会改变，所以可以重复利用之前的点，每次新开 $\log$ 个点。记 $rt_i$ 表示第 $i$ 个版本的线段树的根。每个版本一定有一个前驱，那么我们可以将未被修改的区间直接调用原版本的节点，并对新版本的覆盖了修改操作的区间建立新节点。
### [P3834【模板】可持久化线段树 2](https://www.luogu.com.cn/problem/P3834)
权值线段树上二分。
先把序列离散化，然后对于 $l-1$ 到 $l$ 这个版本，我们实际上等价于在 $l-1$ 的版本上，给 $a_l$对应的数位置加 $1$。
差分一下，$[l,r]$ 就等于 $[1,r]-[1,l-1]$。
根为 $rt_i$ 的节点上的值表示 $a_1$ 到 $a_i$ 出现了多少次。
即 $rt_r-rt_{l-1}$ 这棵树上，权值 $[x,y]$ 出现的次数，来进行查询。
### [P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并](https://www.luogu.com.cn/problem/P4556)
树上差分，每个节点上开一个 $cnt$ 数组，表示i出现了多少次，那么节点 $i$ 上出现次数最多的就是 $cnt$ 的最大值。
对于每一颗权值线段树表示这个点上有什么数字，每个数字出现的几次，然后求点i的权值线段树就是将它所有孩子的线段树合并到一起然后再对合并出来的线段树进行一些在这个节点的插入和删除操作。