Segment tree Beats!-526互联

前言

Segment Beats 可以用来解决处理区间最值，区间历史值的问题。

~~不保证这些题都实现过~~。

区间最值操作

HDU5306. Gorgeous Sequence
给出一个长度为 $n(n\le 10^6)$ 的序列 $A$ 和 $m(m\leq 10^6)$ 次操作，每次操作为以下三种类型之一：

给出 $l,r,k$，对于所有 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,k)$；

给出 $l,r$，求序列 $A$ 区间 $[l,r]$ 的最大值；

给出 $l,r$，求 $\sum_{i=l}^{r}A_i$。

我们考虑这样一个做法，维护区间最大值 $mx$ ，最小值 $mn$，和 $sum$ ，然后对于修改，如果 $mx\le k$ 就直接退出，$mn\ge k$ 就区间赋值，否则就递归，这是一个 $O(n^2\log n)$ 的做法，很明显过不了。

我们换一种方式，记录区间的最大值 $mx$，最大值个数 $cnt$，和区间严格次大值 $se$。那么对于一次修改，有三种情况。

$mx\le k$，此时直接退出。
$se<k\le mx$，对最大值打上修改 $tag$ ，这里用赋值或者加法标记都可以，根据 $cnt$ 修改 $mx,sum$，退出。
$k\le se$，在这种情况下，我们递归处理。

这个做法看起来暴力，但是可以证明这个做法的时间复杂度是 $O((n+m)\log n)$ 的。

我们令这个节点的最大值和其父亲最大值不同的节点为关键点。

设一次操作中的关键点点数为 $A$，则访问的总点数是 $O(A\log n)$ 的，我们花费的时间为 $O(A\log n)$，而关键点个数减少了 $A$。

刚开始的时候有 $O(n)$ 个关键点，所以总时间复杂度是 $O((n+m)\log n)$ 的。

这种划分最值与非最值，然后转化成加减修改的做法是区间最值操作的核心，请牢牢记住。

例题二
给出一个长度为 $n(n\le 10^6)$ 的序列 $A$ 和 $m(m\leq 10^6)$ 次操作，每次操作为以下四种类型之一：

给出 $l,r,k$，对于所有 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,k)$；

给出 $l,r,v$，对于所有 $i\in[l,r],A_i\gets A_i+v$ 。

给出 $l,r$，求序列 $A$ 区间 $[l,r]$ 的最大值；

给出 $l,r$，求 $\sum_{i=l}^{r}A_i$。

这道题我们沿用上一题的思路，将维护的元素分成最大值和非最大值两类，分开维护。

对于这个做法，论文中给出了一个 $O(n\log n+m\log^2n)$ 的证明。

同样，我们令这个节点的最大值和其父亲最大值不同的节点为关键点。

设每次 $1$ 操作的减少了 $A$ 个关键点，则代价为 $O(A\log n)$，然后每一次 $2$ 操作，最多令线段树上修改的 $O(\log n)$ 个节点成为关键点，所以总关键点数是 $(n+m\log n)$ 的，时间复杂度为 $O(n\log n+m\log^2 n)$ 。

UOJ#515. 【UR #19】前进四
给出一个长度为 $n(n\leq 10^6)$ 的序列 $A$ 和 $q(q\leq 10^6)$ 次操作，每次操作为以下两种类型之一：

给出 $x,v$，将 $A_x$ 变成 $v$；

给出 $x$，求 $A_x,A_{x+1},\cdots,A_n$ 的不同后缀最小值个数。

考虑到询问的是后缀，我们可以对下标从后往前扫描线，维护每一个时刻 $A_x$ 的值，如果一个时刻的 $A_x$ 小于之前这个时刻的历史最小值，那么我们就令这个时刻的答案加 $1$，转化成区间取 $\min$ ，如果被修改到就加 $1$ 的问题，这个很好维护。

CF1290E Cartesian Tree
给你一个排列，对于每一个 $k\in[1,n]$，求出只保留 $[1,k]$ 时，建大根笛卡尔树所有节点的子树大小之和。

先考虑对于 $k$ 等于 $n$ 怎么做。

对于下标 $i$，记 $i$ 左边第一个大于它的下标为 $lst_i$，下一个为 $nxt_i$，则下标 $i$ 的子树大小为 $nxt_i-lst_i-1$。

然后大小之和即为 $\sum nxt_i-\sum lst_i-n$，$nxt$ 与 $lst$ 的维护方法是相同的，我们现在只讨论 $nxt$ 的维护方法。

现在我们令 $k$ 从小到大增加。

我们每次增加了一个比之前的所有数都大的数，所以其左侧的点的 $nxt$ 都应该和 $k$ 的下标取 $\min$ 。

然后我们发现，对于空着的位置，我们是不计入下标的，我们其实是在插入，然后右侧的点的下标都会加 $1$，同时 $nxt$ 也会加 $1$ 。

我们就把这个题转化成了区间取 $\min$，区间加，单点修改，全局求和的问题。

Picks loves segment tree V
维护 $A,B$ 两个数组，对 $A$ 数组区间取 $\max$，区间加，询问区间 $A_i-B_i$ 的最大值和最小值。

我们将区间中的下标分为四种：$A,B$ 同时为最小值，$A$ 为最小值但 $B$ 不是，$A$ 不是最小值但 $B$ 是，$A,B$ 都不是最小值。

然后对于这四种情况分别处理，维护一下区间 $A,B$ 最小值，次小值，四类的 $A-B$ 最值。

我们发现这种做法能拓展到 $K$ 个数列的情况，时间复杂度 $O(2^Km\log^2 n)$，空间复杂度 $O(2^K n)$。

Dzy loves segment tree
区间取 $\min$，区间加，询问区间 $\gcd$。

我们同样分为最大值和非最大值，对非最大值差分，加减变成对差分部分做单点加，对非差分部分区间加，分开做就可以了。

复杂度 $O(n\log^3 n)$。

CF997E Good Subsegments
给出长度为 $n$ 的一个排列。

定义一个集合是连续的,当且仅当 $\max S-\min S+1=|S|$

$q$ 次询问某个区间 $[l,r]$ 有多少个子区间是连续的。

这个大家可以自己思考一下。

历史最值操作

在完成接下来的例题前，请大家记住一点，我们的懒标记本质是若干个标记形成的队列的等价标记。

如我们的标记本来是 $q_1,q_2,q_3\ldots q_k$，在平时我们能将其合并成一个等价的标记 $q$。

但在历史值问题中，我们不仅要维护这个等价的标记，还要维护这个标记队列的历史最值的标记 $q'$。

在标记叠加的时候，我们可以从这方面来思考新的标记对原合并的等价标记和在此基础上产生的历史标记带来的影响。

拉一些 cmd 博客里的话过来：

在线段树标记的下推机制中，某个点存有标记，表示整一棵子树在标记存在的时间内都未曾更新。

于是，问题的核心就在于分析单个节点上停留的标记的影响。

在非历史值问题中，我们只关注该节点“当下”的标记是什么，所以我们会直接将标记合并起来。

但在历史值问题中，我们不仅要考虑该节点现在的标记合并结果，还要考虑历史上推来的（按时间为序的）每个标记的依次作用。

为了便于理解，我们不合并标记，假设每个节点上有一个队列（按照时间先进先出），放着所有曾经推过来的标记。

下推标记时，将该节点上所有的标记推到两个儿子处，并清空队列。

于是，我们寻找一种方法 概括一个队列的标记对当前节点的影响。