区间操作杂谈

· · 算法·理论

本文从易到难 （大概） 介绍了一些区间上的经典操作

1.一些线段树水题

查询可合并信息、单点修改/区间修改、区间查询

其中的“可合并信息”可以是 加法、乘法、位运算 及其组合。

前者为线段树板子，不再赘述。

水经验：

区间加，区间查询：P3372 【模板】线段树 1

区间加、乘，区间查询：P3373 【模板】线段树 2

区间修改、区间加、区间求 \max ：P1253 扶苏的问题

重点在于后者，这里给出 （瞎编） 了几道题：

1.

维护长度为 n 的序列，支持区间加，询问区间方差。

方差的定义：

s^2 = \frac{1}{n} \sum( x_i - \bar x )^2

其中 \bar x = \frac{\sum x_i}{n}

稍微化一下式子：

s^2 = \frac{1}{n} (\sum x_i^2 - \sum 2x_i \bar x + \sum \bar x^2) = \frac{1}{n} (\sum x_i^2 - 2 \bar x \cdot n\bar x + n \bar x^2 ) = \frac{1}{n} \sum x_i^2 - 2 \bar x^2 + \bar x^2 = \frac{1}{n} \sum x_i^2 - \bar x^2

于是只需维护 区间和 以及 区间平方和 即可。

考虑怎么维护 区间加：

对于 区间和，直接加上即可；

对于 区间平方和，每一项由 \sum x_i^2 变为 \sum (x_i + v)^2 即 \sum x_i^2 + 2 v \sum x_i + v^2 。

那么一次 区间加 对 区间平方和 的影响为 2v \sum x_i + v^2 。

于是每次 区间加 的时候对 区间平方和 加上这部分即可。

题目：

P5142 区间方差

P1471 方差

P2122 还教室

2.

维护长度为 n 的序列，支持区间加，询问区间内所有有序数对两数乘积之和。

其实就是求

\sum_{i \in [l,r]} \sum_{j \in [i+1,r]}a_ia_j

的值。

交换下求和顺序：

(\sum_{i \in [l,r]} a_i)(\sum_{j \in [i+1,r]} a_j)

首先觉得这个式子不顺眼，将其乘二：

(\sum_{i \in [l,r]} a_i)(\sum_{j \in [l,i-1] \cup [i+1,r]} a_j)

觉得 j 后面那坨东西不好看，加上 \sum a_i^2 把它去掉：

(\sum_{i \in [l,r]} a_i)(\sum_{j \in [l,r]} a_j)

也就是：

(\sum_{i \in [l,r]} a_i)^2

于是题目就是求：

\frac{1}{2}((\sum_{i \in [l,r]} a_{i})^{2} - \sum_{i \in [l,r]}a_{i}^{2})

于是维护下 区间和 以及 区间平方和 就行了。

3.

P4513 小白逛公园

维护长度为 n 的序列，支持单点修改，查询区间内最大子段和。

经典题。

“最大子段和”显然不是一个可合并信息。

于是考虑将其拆分成几个可合并信息。

大力分类讨论：当前区间的最大子段和 越过/未越过 两个子区间分界线。

如果未越过分界线，取两个子区间的 最大子段和 即可；

如果越过分界线，将这个最大子段从分界线处分开，拆分成 左子区间的右起最大子段和 + 右区间的左起最大子段和。

如果能维护出右起最大子段和和左起最大子段和，就能计算出两种情况的最大子段和，当前区间的最大子段和就分别它们取 \max 即可。

接下来只需考虑区间内右起最大子段和和左起最大子段和怎么维护。

再大力分类讨论：当前区间的右起最大子段和越过/未越过 两个子区间分界线。

如果未越过分界线，取右区间右起最大子段和；

如果越过分界线，取左区间右起最大子段和+右区间区间和。

左起最大子段和同理。

于是一个区间需要维护 4 个信息：最大子段和，右起最大子段和,左起最大子段和，区间和。

4.

P3792 由乃与大母神原型和偶像崇拜

单点修改，查询区间 [l,r] 是否可以重排为值域上连续的一段

判断问题是比查询问题要简单的，于是考虑乱搞做法：

显然的，如果 [l,r] 符合要求，那么重排序列为 \min_{i \in [l,r]} \{ a_i \} ,..., \max_{i \in [l,r]} \{ a_i \} 。

首先判断这个重排序列的长度，其次判断这个序列的一个与顺序无关的特征。

可以取区间和以及区间平方和，当然也可以取区间异或和之类的乱搞判断，本质就是一种与顺序无关的哈希。

区间平方和判断时注意值域溢出。

5.

P2056 [ZJOI2007] 捉迷藏

给出一棵 N 个有色(黑白，黑色对应关灯，白色对应开灯)节点的树以及 M 次操作，
每次操作将改变一个节点的颜色或者求出树上最远的两个黑点距离

实际上就是求所有黑点构成树的直径。

对编号为 1 \sim n 的点建线段树，线段树上区间 [l,r] 维护这些点构成树的直径长度。

考虑如何合并信息：设左区间为 [l,mid] ，右区间为 [mid+1,r] ，合并后新区间的直径两端点定为 左区间及右区间的直径两端点 共四个点其中之一。

于是线段树上维护 [l,r] 这些点组成的树的直径长度，直径两端点，然后暴力合并即可。

单点修实现显然。

后记：实际上这题正解是淀粉树，但我不会。

类似的题但我不会写（动态维护直径满血版）：P6845 [CEOI2019] Dynamic Diameter

一些题：

如题：P6327 区间加区间 sin 和

区间加等差数列，单点查询：P1438 无聊的数列

挺有意思的题：P4588 [TJOI2018] 数学计算

同上：P8862 「KDOI-03」还原数据

2. 一些杂题

P1972 [SDOI2009] HH的项链

给定一序列 a，每次询问区间内数字种类数。

经典题。

一个经典而巧妙的 trick：对第 i 个数维护 pre_i ，表示 在 [1,i-1] 内满足 a_j = a_i 的最大 j （上一个 a_i 出现的位置）如果 j 不存在，就令 pre_i = 0 。

询问一段区间内数字种类数，等价于一段区间内第一次出现的数的个数（废话）。

因次我们无需关心重复出现的数的个数，只需关心第一次出现的数的个数。

而如果一个数 a_i 在区间内第一次出现，那么它的前一个数的位置 pre_i 一定在区间之前 或 不存在。即 pre_i \in [1,l-1] 或 pre_i = 0 。

那么 区间数的个数 = 区间第一次出现的数的个数 = 区间内 pre_i \in [0,l-1] 的个数，也就是 \sum_{i\in[l,r]} [pre_i\in[0,l-1]] 。

用主席树简单维护下就没了。

双倍经验

P2048 [NOI2010] 超级钢琴

求区间内长度在 [L,R] 内的前 k 大子段和 的总和。

先考虑怎么维护区间最大子段和：

直接正面硬刚不怎么好做，考虑维护一个前缀和。

对于一个子段 [l,r] ，其子段和为 s_r - s_{l-1} ，那么以 l 为左端点的区间最大子段和在 s_r 取最大值时取到。

由于 r \in[l+L-1, \min \{ l+R-1, n \}] ，于是可以通过维护区间最大值来确定 l 为左端点的区间最大子段和。扫一遍全体取 \max 就得到了区间最大子段和。

然后考虑怎么维护前 k 大子段和：

对于每一个左端点，维护一个三元组 (l, r_l, r_r) ，分别表示当前左端点 以及 右端点的范围，这样每个最大子段和都唯一对应了一个三元组。

先枚举左端点把初始的三元组 (l, l+L-1, \min \{ l+R-1, n \}) 都扔进堆里面，按区间最大子段和排序。

每次取出当前最大子段和对应的三元组 (l,r_l,r_r) ，同时维护最大值取到的位置 pos ，记录贡献的同时将区间拆为 (l, r_l, pos-1) 和 (l, pos+1, r) ，重新扔进堆里面。

插入与弹出的数个数是 O(k) 级别的，每次插入需要 O(\log n) 计算区间最大值，同时 O(\log k) 堆维护信息， k 与 n 同阶，总体复杂度大概是 O(n \log^2 n) 的。

当然也可以用 ST 表使 RMQ 的部分优化到 O(n \log n)-O(1) ，但没必要。

口胡另外一个做法：对每个左端点 l 维护一个数 cnt_l ，初始均为 1 ，表示查询以 l 为左端点的区间第 cnt_l 大的值。于是就转化为了一个区间第 k 大问题，用主席树维护即可。

未完待续...