前言：本文由aaa巨佬写成，原文link here。

线段树

核心要点：

线段树主要维护信息和标记。

对于以下操作若能够做到 $O(k)$ 合并：

信息+信息；

标记+标记；

标记+信息；

那么线段树即可做到 $O(n k \log n)$ 维护区间信息。

例题

P6327 区间加区间 sin 和

套和差角公式即可，简单题。

时间复杂度 $O((n + q) \log n)$。

P7706 「Wdsr-2.7」文文的摄影布置

由于单点修改很容易做到 $O(\log)$，所以我们只需要考虑如何合并区间信息就行了。

这题可以考虑和小白那题一样的策略，维护 $ma, mb, lma, rma, tma$ 分别表示 $a$ 的最大值， $b$ 的最小值， $\max_{i} \max_{j > i} a_i - b_j$，$\max_{i} \max_{j < i} a_i - b_j$，和当前区间的答案。

容易得出以下转移方程：

$ma = \max(L.ma, R.ma)$

$mb = \min(L.mb, R.mb)$

$lma = max(L.lma, R.lma, L.ma - R.mb)$

$rma = max(L.rma, R.rma, R.ma - L.mb)$

$ tma = max(L.tma, R.tma, L.lma + R.ma, R.rma + L.ma) $

时间复杂度 $O((n + q) \log n)$。

P4344 [SHOI2015] 脑洞治疗仪

（傻逼题意，读了 $10$ 分钟）

可以发现操作可以通过线段树二分转化为区间赋值。

时间复杂度 $O((n + q) \log n)$。不会线段树二分可以写 $O((n + q) \log^2 n)$，也能过。

无题号

题意：

给你一个长度为 $n$ 的序列，有 $m$ 个操作：

1: 单点修改；

2: 区间查询有没有重复的数字。

数据范围：$1 \leq n,m \leq 5 \times 10^5$。

由于是单点修改，考虑没有修改的时候怎么做。

可以考虑维护每一个数字和后继 $ne_i$ 满足 $ne_i$ 是满足 $a_i = a_{ne_i}$ 的最小的 $ne_i$。

可以维护区间的最小后继 $max_{ne}$，若 $max_{ne}$ 小于等于区间的右边界，那么显然是有重复数字的。

至于单点修改，稍微分析一下会发现可以转换为多个单点修改，用 $set$ 稍微维护一下就可以了。

时间复杂度 $O((n + m) \log n)$。

Codechef DGCD（弱化版）

题意：

给你一个长度为 $n$ 的序列，有 $m$ 次操作：

1: 区间加

2: 求区间中所有数的最大公约数

数据范围：$1 \leq n,m \leq 10^5$，$1 \leq a_i \leq 10^9$。

考虑这样设计一个区间的信息，一个区间存储它的左端点 $a_l$ 和 $ gcd(a_{l + 1} - a_{l}, a_{l + 2} - a_{l + 1}, \cdots, a_[r] - a_{r - 1}) $。

这样，原本是区间加的修改就变成的单点修改！

而显然，一段区间的 $gcd$ 就是 $\gcd(a_l, x)$！

合并区间是显然的。

时间复杂度 $O((n + m) \log n \log V)$，其中 $V$ 是值域。

P5278 算术天才⑨与等差数列

很显然，只要满足以下条件即可：

1: 最大值减最小值要满足条件

2: 数互不重复

3: 差分数字的 $gcd$ 为 $k$

用上面讲的知识维护就可以了。

时间复杂度 $O((n + m) \log n \log V)$。

P6617 查找 Search

和前面有一题一样，维护前驱后继即可。

可以用支配优化，每次后继只记录最接近的。

时间复杂度 $O((n + q) \log n)$。

势能线段树/颜色均摊

例题

P4145 上帝造题的七分钟 2 / 花神游历各国

势能线段树模版题。

时间复杂度 $O(n \times \log n \times \log \log V)$。

CF438D The Child and Sequence

取模 = 除以2

时间复杂度 $O((n + q) \times \log n \log V)$。

P9989 Ynoi Easy Round 2023 TEST_69

显然，一个数最多被 gcd $O(log)$ 次就会变成 $1$。

所以若一个区间的 lcm 是 x 的因数，那么这个区间就不用被 gcd，否则肯定有一个数要被 gcd。

稍微分析一下可以额发现时间复杂度为 $O(n \log n \log V)$。

记得开 __int128。

Naive Operations

妙妙题。

首先考虑，对于一个坐标 $i$，至少要加多少次 $a_i$，才能使得 $[\frac{a_i}{b_i}]$ 加 $1$？

容易发现，只需要加 $\frac{1}{b_i}$ 次即可。

那么最坏情况下，$\frac{a}{b}$ 会被加 $m \times \sum_{i = 1}^n \frac{1}{n} = m \log n$ 次。

所以考虑用一个线段树维护 $b - a$ 的最小值即其坐标，另一个线段树维护 $[\frac{a}{b}]$。若存在 $i$ 使得 $b_i - a_i = 0$，那么 $ [\frac{a_i}{b_i}] \leftarrow [\frac{a_i}{b_i}] + 1 $，然后 $b_i - a_i \leftarrow b_i$。

时间复杂度 $O((n + m) \log n \log n)$。

ZQC 的手办

考虑如何求出一个区间的前 $k$ 小，可以发现以下策略：

先求出第一小和它的坐标，然后设为 $\inf$，然后在求出第二小和它的坐标，然后设为 $\inf$ $\cdots$

这样可以在 $O(x \log n)$ 的时间复杂度内求出前 $x$ 小。

至于区间 $max$ 可以标记永久化解决。

时间复杂度 $O(\sum x \log n)$。

CF280D k-Maximum Subsequence Sum

两种做法：

法1：闵可夫斯基和（$O(n k \log n)$，略）

法2：反悔贪心。

选一个最大连续字段和，然后将选的区间全部乘上 $-1$。

证明需要模拟费用流。

时间复杂度 $O(n k \log n)$。

CF444C DZY Loves Colors

又是势能线段树模版题/颜色均摊模版题。

可以发现相邻点的颜色会越来越相似，所以可以记录一个区间的颜色是否相同。若相同直接区间修改打标记即可。

时间复杂度 $O((n + m) \log n)$。

CF1638E Colorful Operations

打 lazytag 来延迟区间加即可。

用势能线段树和颜色均摊模型都可以做。

时间复杂度 $O((n + q) \log n)$。

CF453E Little Pony and Lord Tirek

设一段颜色代表这段区间上一次推平的时间是相同的。

对于一段颜色用主席树即可。

时间复杂度 $O((n + m) \log n)$。

后记：lxl是四川的男生！