Preview：
终于到了喜闻乐见的线段树了，因为其灵活度较高，基本框架固定，深受像我这样喜欢水题的人的喜爱。
而至于为什么文章名叫“线段树和树状数组”呢，实际上我们可以把树状数组看做成没有右儿子的线段树，然后加的时候是直接进行的 pushup，然后这样树状数组是否就清晰多了呢？
板子：
因为本人太懒了，所以懒得打板子了。
详情可见树状数组 1、2，线段树 1、2，普通平衡树，可持久化线段树 1、2，线段树 3。
例题：
Preface:
为什么会有这一栏呢，原因是因为自己太懒了，懒得打代码，然后如果有什么题自己能直接口胡出来就写到这里口胡。
P2023 [AHOI2009] 维护序列（线段树 2）：
考虑线段树，维护两个 tag，加和乘。
乘的时候别忘了给加的 tag 也乘上。
千万别忘了取模。
先乘后加。
P1471 方差：
\(trick\)：拆式子
线段树，操作 1、2 都是经典操作，这里不多赘述。
重点考虑操作 3。
听起来不想很能维护的样子，但是这里面有个 \(\text{trick}\)，对于你认为不大可能维护的东西，我们可以尝试拆式子来分开维护：
对方差的公式拆个式子：
所以我们可以清楚地看到，对于方差，我们只需要维护其区间和 sum 和平方和 sqrsum 即可。
然后就是注意精度。
P6327 区间加区间sin和：
我表示差角公式直接套版。
CDQZ Challenge 5：
有两种思路，先说第一种：
对于操作 \(2\)，我们可以观察一下，发现其本质是区间和的平方减去区间平方和再除以 \(2\)，所以让线段树维护区间和和区间平方和就可以了。
至于操作 \(3\) 嘛，因为只是单点修改，所以怎么乱搞都可以过。
第二种是机房 \(\text{gxd}\) 大神提出来的（膜拜大神 \(\text{gxd}\)）：
对于一个区间，我们维护两个值，分别是两两相乘的值和区间和，对于区间的合并，我们则有：
然后就做完了，毕竟是单点改，所以修改操作也是 \(O(M \log n)\) 的。
以上两种的时间复杂度都是 \(O(n \log n)\)
PS：更多关于 CDQZ Challenge 的内容，可以看我的这篇博客
P4513 小白逛公园：
\(trick\)：区间连续段最值问题
考虑用线段树维护。
我们可以发现一件事情，若我们要合并两个区间，那么对于合并区间内的区间最大值来说，它要么是左区间最大值，要么是右区间最大值，要么既不是左区间最大值，也不是左区间最大值。
前两类十分好想，但是最后一类该怎么办呢？
考虑一下如果不是左区间最大值，也不是右区间最大值，那么可能存在的区域只可能会是两个区间的交界处，此时我们只需要维护一个前缀最大值和后缀最大值，然后将左区间的后缀最大值和右区间的前缀最大值拼接在一起，就是第三类情况。可以得证，这种拼接方式即使第三类最大值。
综上，对于每个线段树上的节点，维护前缀最大值，后缀最大值和区间最大值即可。
剩下就是板子了。
PS：可以去尝试一下 GSS 题目，十分小清新。
P7706 「Wdsr-2.7」文文的摄影布置：
\(trick\)：维护区间非连续点最值问题 \(\Leftrightarrow\) 维护区间连续段最值问题
PS：上述的等价指的是方法等价
一道非常有意思的题目。
题目可以转化成如下问题：
显然，原式可以直接转化为：
证明显然。
此时，我们思考如何从子区间合并上来。
还是依照 P4513 的思路，考虑最优的答案会出现在哪里。
则显然，父区间的答案只会在左区间答案、右区间答案、区间交界处答案取到。
左右区间的答案可以直接维护，但是区间交界处我们就得需要分类讨论了。
首先，因为答案分散在两个区间，所以 \(A_i\) 和 \(A_k\) 此时显然就不在同一个子区间内，故我们只需要考虑 \(B_j\) 会在哪个区间内就行了。
此时，对于两个子区间，就需要维护如下式子：
然后你就又会发现，诶 \(\text{TMD}\)，这个也没法直接维护啊！！
于是设 \((1)\) 式为 \(P(l,r)\)，\((2)\) 式为 \(Q(l,r)\)。
然后考虑怎么维护。
于是又双叒叕可以参考 P4513 的思路，发现对于 \(P(l,r)\) 和 \(Q(l,r)\)，我们继续考虑最优的答案会出现在哪里。
则显然，父区间的答案只会在左区间答案、右区间答案、区间交界处（？）答案取到。
这里的区间交界处是什么意思呢，即 \(A_i\) 或 \(A_k\) 与 \(B_j\) 不在同一个子区间内。
所以对于父区间 \(P(l,r)\) 和 \(Q(l,r)\)，就出现了如下维护方式：
所以，对于 \(\Psi(l,r)\) 的维护，我们就出现如下式子：
最后就是套板子了。
P5278 算术天才⑨与等差数列
对这个题目，有两种思路：
Solution 1：
\(trick\)：线段树维护 \(Hash\)。
考虑 Hash，可以参考此题弱化版 P3792 由乃与大母神原型和偶像崇拜。
Hash 的值可以是区间和，区间平方和，区间立方和，反正 Hash 嘛。
PS：该做法可能会被卡掉，不过如果你可以选择多维护几个 Hash 值。
时间复杂度 \(O(m \log n)\)
Solution 2：
差分，将原问题转化为区间 \(\gcd\) 问题，则此时的 \(\gcd\) 的数值应该是公差 \(k\)。
至于不出现相同数字嘛，维护前驱，变成数点问题。
时间复杂度 \(O(m \log^2 n)\)
然而可以去掉一只 \(\log\)，考虑一下，实际上只需要维护区间前驱最大值就行了。
时间复杂度 \(O(m (\log n + \log v))\)
P4344 [SHOI2015]脑洞治疗仪：
本题两种思路：
Solution 1：
\(\text{trick}\)：线段树上二分
实际上当把这个 \(\text{trick}\) 写出来的时候，这个题就真的没有什么思维难度了。
无非就是区间推平 + 区间连续段最值问题而已。
如果我们不考虑在线段树上二分，则是直接二分开始推平的位置。
时间复杂度 \(O(m \log^2 n)\)
但是如果你会线段树上二分的 \(\text{trick}\)，你就可以去掉一只 \(\log\)，时间复杂度优化成 \(O(m \log n)\)
虽然 \(\log^2 2 \times 10^5\) 也不算特别大，但是对 \(1\text{s}\) 的时限来说还是有点紧张了。
Solution 2：
珂朵莉树
没了。
P2572 [SCOI2010] 序列操作：
\(trick\)：全套 01 序列操作。
对，这题没啥难度，但是就是纯纯恶心人。
注意一下取反的时候也别忘了把推平的 tag 给取反就行。
P6492 [COCI2010-2011#6] STEP：
小白逛公园的 \(\text{Easy Version}\)。
不过需要考虑合并可行性。
P2894 [USACO08FEB] Hotel G：
感觉很像 P4344，不过就是如果住不下就直接不住了，P4344 是住不下就舍掉一部分而已。
CF438D The Child and Sequence
\(trick\)：势能操作。
其他两个操作都很简单，重点来考虑取模操作。
首先考虑每次取模操作所带来的影响，会发现实际上每次取模之后，所有数要么缩小，要么不变。
考虑维护区间最大值，如果区间最大值大于等于待取模数我们就暴力往下修改，直到某个区间的最大值小于待取模数或者到达叶子节点时再停下。
乍一听好像时间复杂度十分不可取，实际上均摊一下复杂度是 \(O(n \log n)\) 的。
CF240F TorCoder
\(trick\)：开一车线段树。
使用这个 \(\text{trick}\) 的前提是开的线段树的个数要足够小，且应该是 \(O(m \log n)\) 的复杂度给了 \(2 \sim 3 \text{s}\) 时限，然后感觉直接维护好像不大好做的题目。
（或者说是直接用来骗分）
思考一下，对于构造回文串，我们只需要分两类讨论：
-
当需要构造的长度为偶数时，我们需要每一种颜色的数量都为偶数。
-
当需要构造的长度为奇数时，我们需要有一种颜色的数量为奇数，其余都为偶数。
然后就是开 \(26\) 棵线段树，维护一下每个颜色的位置，转化为 01 序列问题。
注意空间。
CF431E Chemistry Experiment
\(trick\)：线段树优化二分答案
看到 \(\text{trick}\) 名，你可能感觉很怪，实际上我也觉得很怪，但是实际上就是这样，用线段树来优化二分答案的 check 部分，使得 \(O(mn \log n)\) 的复杂度降低到 \(O(m \log^2 n)\)
本题维护一个值域线段树，动态开点，支持区间和和值域区间有效个数和。
考虑二分答案 \(\bar v\)，表示倒完水后有水部分最大的体积。
注意精度。
P1438 无聊的数列
\(trick\)：原序列转化。
emm……感觉这个 \(\text{trick}\) 用途太广了，应该是个人人都会的技能吧。
考虑对原序列差分，因为是单点查询，所以差分后就变成区间查询了。
然后就是考虑等差数列修改，因为等差，所以相当于是区间加，然后再在 \(r+1\) 处减掉 \(D \times (r-l) + K\) 就行了。
哦对了，别忘了在 \(l\) 处加上 \(K\)。
PS：是不是树状数组也能做啊/yiw
CF992E Nastya and King-Shamans
考虑将原序列转化为前缀和，则此时单点修改就变成了在前缀和序列上区间修改。
然后考虑用 rmq 线段树维护原序列与前缀和的差值，此时，每次单点修改就变成了区间减和单点加。
查询就向下递归区间最大值 \(\ge 0\) 的节点。
为什么复杂度是正确的呢？
因为题目保证，任何时候 \(a_i\) 都小于等于 \(10^9\)，因而我们可以发现，满足条件的点最多最多不会超过 \(\log 10^9\) 个，毕竟每一个符合条件的点都会导致前缀和倍增。
时间复杂度 \(O(m \log n \log v)\)。
可能需要减减常数，这个时限不是很健康。
CF1000F One Occurrence：
咕咕咕，我是鸽子
CF1149C Tree Generator™
\(trick\)：括号序列\(\Leftrightarrow\)树的欧拉序
在讲作法之前，我不得不承认，刚开始的时候，确实被这道题给耍了，这个傻子刚开始满脑子想的都是 \(\text{LCT}\) 啊。
这题我认为是诈骗题的 master（也可能只有我这么傻，ε=(´ο｀*)))唉）
将所有左括号看做成 \(1\)，将所有有括号看成 \(-1\)，然后不就是最大字段和……吗？
如果你认为是最大子段和 \(+1\) 的话，你又被诈骗了（叹气。
如果考虑最大子段和的话，你会发现，你给无根树定死了根节点，但是像如下样例的情况你就处理不了了:
输入：
((()))((()))
最大子段和 + 1：
3
答案：
7
所以再次观察括号序列，发现树的直径就是括号序列的最长去匹配区间。
然后我们可以发现如下 \(\text{Lemma}\)：
最长去匹配区间 = \(\max_{1 \le l < p < r \le n} \{v_{p+1,r}-\,v_{1,p}\}\)
然后原问题被转化成了如何求最大子段相邻区间差 \(\Delta\)（以下简写为 \(\Delta\)），即：
考虑一下线段树怎么维护（大家好，我喜欢暴力数据结构……）这个看起来十分难以维护的东西。
这里我使用的是逆向分析法（具体思路可以参考一下 P7706）：
首先，考虑最终答案需要什么贡献，对于一个区间的 \(\Delta\)，它要么是左半区间的 \(\Delta\)，要么是右半区间的 \(\Delta\)，要么是当前区间的最大相邻区间差 \(\delta\)，要么是右半区间的前缀 \(\Delta\) 减去左半区间的后缀最小值，要么是左半区间的后缀 \(\Delta\) 加上右半区间的前缀最大值。
然后你就发现，这个最终答案的维护十分抽象，好像需要 \(9\) 个值，分别是前缀子段和的 min 和 max，后缀子段和的 min 和 max，前缀的 \(\Delta\)，后缀的 \(\Delta\)，区间的 \(\delta\) 和 \(\Delta\)，区间的 sum。
因为剩下的维护太 naive 了，所以懒得写了。
交换操作就是单点取反，\(1 \rightarrow -1, \, -1 \rightarrow 1\)
小结
感觉这份博客的水题好像有点多了，抽时间再写个 \(2\)。