线段树、平衡树基础练习

从课件库里翻出来的线段树、平衡树练习。

LOJ 10129 「一本通 4.3 练习 3」维护序列

线段树如果有多个懒标记，下传顺序可能很重要。

题意

• 区间全部 $\times k$；
• 区间全部 $+k$；
• 求区间和 $\bmod m$。

$n,q\le 10^5$，$m\le 10^9$。

link: https://loj.ac/p/10129

思路

维护懒标记为一个函数 $x\to kx+b$，下传标记时根据目前区间长度以及目前区间和，计算出新和是平凡的；标记合并直接函数复合。

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

代码

https://loj.ac/s/1436978

Luogu 4513 小白逛公园

线段树经典的维护“跨过 mid”的答案思想的运用。

题意

• 单点修改；
• 区间查最大子段和。

$n\le5\times 10^5$，$q\le 10^5$。

link: https://www.luogu.com.cn/problem/P4513

思路

考虑在线段树上维护，那么仅需考虑跨过 $mid$ 的区间。容易知道这是由一个左儿子的后缀和一个右儿子的前缀拼成的。额外维护最大前缀和与最大后缀和即可。

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

代码

https://www.luogu.com.cn/record/46114702

NOI 2005 维护数列

使用 Splay 维护序列树的模板。

题意

维护一个数列，支持以下六种操作：

• 在下标 $pos$ 后插入 $m$ 个数 $v_1,\dots,v_m$；
• 删除下标 $[l,r]$ 的所有数；
• 将下标 $[l,r]$ 统一修改为 $c$；
• 翻转 $[l,r]$；
• 求 $[l,r]$ 和；
• 求全局最大子段和。

保证操作合法，任何时候数列最多含有 $5\times 10^5$ 个数，插入数字总数不超过 $4\times 10^6$，值域 $[-10^3,10^3]$，操作数 $M\le 2\times 10^4$, ML 128MB.

link: https://www.luogu.com.cn/problem/P2042

思路

使用 Splay 维护。

懒标记：修改标记和翻转标记。下传顺序无所谓。

维护信息：子树大小（找到第 $k$ 位）、区间和、区间最大前缀和、区间最大后缀和、区间最大子段和（常规查询）。

时间复杂度 $O(q\log |S|)$。

代码

https://www.luogu.com.cn/record/75554664

JLOI 2011 不等式组

简单的不等式转化。

题意

维护一个不等式组，支持以下操作：

• 向组内添加 $ax+b>c$；
• 删除添加的第 $i$ 条不等式；
• 查询 $x$ 满足多少条不等式。

操作数 $n\le 10^5$，$a,b,c\in[-10^8,10^8]\cap\mathbb Z$，$k\in[-10^6,10^6]\cap\mathbb Z$，ML 125MB.

link: https://www.luogu.com.cn/problem/P5482

思路 1

首先分类讨论 $a$：

• 若 $a=0$，则 $ax+b>c$ 等价于 $b>c$；
• 若 $a<0$，则 $ax+b>c$ 等价于 $x\ge \left\lceil\dfrac{c-b}{a}\right\rceil$；
• 若 $a>0$，则 $ax+b>c$ 等价于 $x\le \left\lfloor\dfrac{c-b}a\right\rfloor$。

离散化后使用树状数组分别维护 $\ge$ 和 $\le$ 的不等式（具体地，维护 $\ge k$、$\le k$ 的不等式的个数），查询直接查。

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

思路 2

同上，但是使用平衡树维护，查询查 rank。

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

代码

思路 1：https://www.luogu.com.cn/record/75564611

Luogu 1471 方差

常规的维护区间和、区间平方和以计算区间内二次式。相关的题还有 SDOI 2017 相关分析。

题意

维护一个序列，支持以下操作：

• 区间加；
• 求区间和；
• 求区间方差。

长度 $n\le 10^5$，操作 $m\le 10^5$，ML 125MB。

思路

根据方差的定义，

$$s^2=\dfrac 1n\sum(x-\bar x)^2=\dfrac 1n\sum x^2+\bar x^2$$

于是我们只需要维护区间和和区间平方和。区间平方和的 lazy tag 修改用完全平方公式即可。注意区间平方和要先于区间和更新。

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

代码

https://www.luogu.com.cn/record/75581392

CDQZ OpenJudge DS Challenge 4

维护跨过 mid 的答案，或是维护二次方和。

题意

维护一个序列，支持以下操作：

• 单点修改；
• 求区间内相邻两数乘积和；
• 求区间内两两乘积和。

对 $10^9+7$ 取模，长度 $n\le 10^5$，操作 $m\le 10^5$，ML 256MB.

link: http://cdqz.openjudge.cn/ds/1004

思路 1

建立线段树，维护每个结点的两个询问的答案，合并的时候只需要计算多的答案。

对于相邻两数乘积，多的答案为左儿子的最右端的值乘上右儿子的最左端的值；

对于两两乘积，多的答案为左儿子的和乘上右儿子的和。

维护两个询问的答案、区间和、区间左右端点值即可。

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

思路 2

注意到区间内两两乘积的值为 $\dfrac12\left((\sum x)^2-\sum x^2\right)$，因此可以通过维护区间平方和和区间和来维护区间两两乘积和。

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

代码

http://cdqz.openjudge.cn/ds/solution/34362522

Luogu 4198 楼房重建

一道有趣的序列题。

题意

有 $n$ 个平面上的线段，每条线段垂直于 $x$ 轴，且第 $i$ 条线段的下端点为 $(i,0)$。称第 $i$ 条线段“能被看到”当且仅当如果视线段可以遮挡光线，则第 $i$ 条线段有无限多个点能够被位于 $(0,0)$ 的点光源射出的光线照射到。

有 $m$ 次操作，每次操作更改一条线段的长度，每次操作后问目前有多少条线段“能被看到”。

$n,m\le 10^5$，上端点 $x\in[1,10^9]\cap\mathbb Z$，ML 125MB.

link: https://www.luogu.com.cn/problem/P4198

思路

注意到答案仅跟斜率有关，设斜率为 $k_1,\dots,k_n$，则询问即求“大于所有前面的数”的数的个数。

建立线段树，维护每个结点的仅考虑当前区间的数的答案以及最大斜率。

设目前需要合并 $u$ 结点的答案。注意到 $ls(u)$ 的所有能看到的线段都会贡献给 $u$，但是 $rs(u)$ 的 $< ls(u).max$ 的答案无法贡献。分类讨论：

• 如果 $ls(rs(u)).max \le ls(u).max$，那么 $ls(rs(u))$ 一定全部被遮挡住，递归到 $rs(rs(u))$ 计算；
• 如果 $ls(rs(u)).max > ls(u).max$，那么 $ls(rs(u))$ 对 $rs(rs(u))$ 的限制强于 $ls(u)$ 的限制，因此只要统计 $rs(rs(u))$ 有多少个数贡献给了 $rs(u)$（通过 $rs(u).ans-ls(u).ans$ 得到），然后递归到 $ls(rs(u))$ 计算即可。

每次 pushup 需要递归 $O(\log n)$ 个结点，每次修改有 $O(\log n)$ 次 pushup，因此时间复杂度 $O(n+m\log^2 n)$。

代码

https://www.luogu.com.cn/record/39317529

JSOI 2008 火星人

因为字符串 hash 需要大量的区间查询，使用线段树很容易维护。

题意

给定一个长为 $n$ 的字符串，维护以下操作：

• 修改第 $i$ 位的字符为 ch；
• 在第 $i$ 位字符后添加 ch 这一字符（若 $i=0$ 表示在串首添加）；
• 查询当前字符串的后缀 $suf_i$ 和 $suf_j$ 的最长公共前缀。

字符串内字符皆为小写英语字母，操作数 $m\le 1.5\times 10^5$，字符串长度 $l$ 始终不超过 $10^5$，询问次数不超过 $10^4$，ML 125MB.

link: https://www.luogu.com.cn/problem/P4036

思路

用字符串 hash 判断字符串相等。因为要插入，所以使用 Splay 维护区间树。仅需额外维护每个结点的 hash 值。

查询的时候二分答案即可。时间复杂度 $O(l_0+m_1\log l+m_2\log^2 l)$。

代码

https://www.luogu.com.cn/record/75648169

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

特征值比对的思想应用很广。维护“前一个值与自己相等的下标”在颜色段题里面很常见。

题意

（实际上是 BZOJ 4373 算术天才⑨与等差数列 的弱化版）

维护一个序列，支持以下操作：

• 单点修改；
• 查询 $[l,r]$ 内的所有数从小到大排列后（不去重）是否恰为一个公差为 $1$ 的等差数列。注意，仅有 $1$ 项的数列被视为等差数列。

$n,q\le 5\times 10^5$，初始值域为 $[1,2.5\times 10^7)\cap\mathbb Z$，修改的目标值 $\le n$。ML 125MB。

link: https://www.luogu.com.cn/problem/P3792

思路 1

考虑比对特征值。

首先维护区间 min，确定需要判断的目标等差数列的首项。

分别把真实序列和目标序列的和、平方和、立方和、乘积等做比较，如果都相等则视为相等。

为了防止被特殊构造数据卡掉，拿到初始序列后全局加上一个随机数。

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

思路 2

事实上本题有确定性在线做法。

考虑一个含有超过 $1$ 项的数列是打乱后的公差为 $1$ 的等差数列当且仅当其不包含重复的数字，且其极差等于长度。

开线段树维护每个结点的前一个与自己值相等的位置，并维护其区间 $\max$。开个数组维护后一个位置。

单点修改就像双向链表修改一样。

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

代码

https://www.luogu.com.cn/record/31378906（思路 1，维护和、平方和、立方和，不加随机数）

BZOJ 4373 算术天才⑨与等差数列

可以特征值比对，也可以考虑使用等差数列的性质。

题意

（实际上是 P3792 由乃与大母神原型和偶像崇拜 的加强版）

维护一个序列，支持以下操作：

• 单点修改；
• 查询 $[l,r]$ 内的所有数从小到大排列后（不去重）是否恰为一个公差为 $k$ 的等差数列。注意，仅有 $1$ 项的数列被视为等差数列。

$n,q\le 3\times 10^5$，值域 $[0,10^9]\cap\mathbb Z$，$0\le k\le 10^9$， ML 128MB，TL 2s，强制在线。

link:

• https://darkbzoj.cc/problem/4373
• https://www.luogu.com.cn/problem/U217542

思路 1

考虑比对特征值。

首先维护区间 $\min$ 以确定目标序列。

比对和、平方和、立方和、乘积等特征值，如果都相等则视两个序列相等。

为了防止被特殊数据卡掉，开始时全局加一个随机数。

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

思路 2

考虑等差数列的性质：一个打乱后的公差为 $k$ 的等差数列一定满足其差分数组每一项取绝对值后的最大公约数恰好等于 $k$。

证明：如果最大公约数不是 $k$ 的倍数，则显然不正确，因为每一项都为 $a_1+kd$；

如果最大公约数大于 $k$，则仍然显然不正确，因为这说明原数组所有数模 $kt$ 同余（$t>1$），那么不可能存在两个相差 $k$ 的项。

进一步地：一个序列是打乱后的公差为 $k$ （$k\ne 0$）的等差数列当且仅当其差分数组每一项取绝对值后的最大公约数恰好等于 $k$，且其极差为项数乘 $k$ 再减 $k$，且无重复数字。

证明：必要性是显然的。充分性：

第一个条件说明其所有数模 $k$ 同余，且不存在 $t>1$ 满足所有数模 $kt$ 同余。极差将这 $n$ 个数限制在 $a_0+kd(d\in\mathbb Z_n)$ 内。无重复数字限制每个数必须恰出现一次。

于是，我们只需要维护：

1. 原数组的 $\min$ 和 $\max$；
2. 差分数组取绝对值后的 $\gcd$；
3. 原数组区间查询是否有重复数字。

第一个条件直接线段树，$O(\log n)$。

第二个条件直接维护似乎是 $O(\log^2n)$ 的，不够优秀。分析一下复杂度：

• 对于 modify，从叶节点 pushup 上去的过程中每个结点维护的值一定会越来越小。对于该叶节点到根的路径，每个父亲一定是儿子的约数。
  • 如果父亲维护的区间 $\gcd$ 与儿子相等，那么 pushup 所调用的 $\gcd$ 在 $O(1)$ 的时间内即会结束；
  • 否则，父亲维护的区间 $\gcd$ 至多是儿子的一半，这种情况只会出现 $O(\log \max{a_i})$ 次。
• 对于 query，只需维护一个全局答案 ans，每次更新答案的时候直接将当前区间 $\gcd$ 与 ans 求 $\gcd$。时间复杂度还是 $O(\log n+\log\max{a_i})$ 的。

对于第三个条件，我们维护每个位置的前一个值与之相等的位置 pre 以及后一个位置 suf。pre 和 suf 可以用离散化/std::unordered_map 和 std::set 维护。为了判断 $[l,r]$ 是否有重复数字，我们只需要维护一个线段树维护 pre 数组的 $\max$ 即可。时间复杂度 $O(\log n)$。

总时间复杂度为 $O(n+q\log (n\cdot\max{a_i}))$。

代码

• https://darkbzoj.cc/submission/191842
• https://www.luogu.com.cn/record/75889683

Luogu 6327 区间加区间sin和

一道简单的懒标记维护题。

题意

维护一个整数序列，支持以下操作：

• 区间加；
• 求区间的 $\sin$ 值之和，保留 $1$ 位小数。

$n,q\le 2\times10^5$，所有数的数都在 $[1,2\times 10^5]$ 内，ML 125MB。

link: https://www.luogu.com.cn/problem/P6327

思路

直接使用 $\sin$ 和 $\cos$ 的和角公式维护区间加。

$$\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta\\ \cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta$$

维护区间 $\sin$ 和 $\cos$ 值分别总和即可。

时间复杂度 $O(n+q\log n)$，如果认为计算三角函数的复杂度为常数的话。

代码

https://www.luogu.com.cn/record/75896707

POI 2015 Logistyka

一道与数据结构结合的贪心题。分开计算贡献的思想值得注意。

题意

维护一个序列，支持以下操作：

• 单点修改；
• 问对当前序列能否进行如下的 $s$ 次操作：“每次选出 $c$ 个正数，把它们都减 $1$”。每次询问之间独立。

$n,q\le 10^6$，值域 $[0,10^9]$，$s\le 10^9$，ML 125MB。

link: https://www.luogu.com.cn/problem/P3586

思路 1

首先先考虑如何对静态区间进行检查。

对于那些 $\ge s$ 的正数，我们可以直接在每次操作中都选择它们，这一定是不劣的；

对于那些 $< s$ 的正数 $x$，注意到它们最多被操作 $x$ 次，因而它们总共最多被操作 $\dfrac{\sum\limits x[x-s]}{c’}$ 次，其中 $c’=c-\sum[x\ge s]$。现在我们证明，整个序列能够进行 $s$ 次操作的一个充要条件是 $\sum x[x< s]\ge c’s$：

必要性：考虑 $s$ 次操作对 $< s$ 的正数的影响。它们总共被减了 $c’s$，但是没有被减到全部为 $0$。

充分性：注意到 $\sum[x< s]> c’$。考虑如下的选择，这是一定可行的：每次取最大的 $c’$ 个数操作。正确性证明：

我们每进行一次操作，就将 $s_t$ 减 $1$（初始为 $s$）。容易知道，任何时刻都有 $\sum x[x< s]\ge c’s_t$。注意到每次一个数最多降低 $1$，因此一个数如果已经 $\ge s_t$，那么它再也不会 $< s_t$ 了。如果某一时刻有 $c’$ 个数达到了 $s_t$，那么直接不断地选择这 $c’$ 个数操作即可；如果某一时刻不到 $c’$ 个数达到 $s_t$，那么我们知道当前的正数个数 $n_t$ 一定满足 $n_t\ge c’$，否则 $\sum x[x< s]\le n_ts_t< c’s_t$，矛盾。

于是，我们对离散化后的权值使用树状数组维护每个值出现的次数（的前缀和）、每个值的真实值乘上出现次数（的前缀和），直接查即可。

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

思路 2

我们还可以直接上平衡树。

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

代码

https://www.luogu.com.cn/record/75914906

Ynoi 2010 y-fast trie

一道简单分类讨论题。注意这种将数分成两种分开算贡献，以及只维护“可能对答案有贡献”的点对的思想。

题意

维护一个集合 $S$，支持以下操作：

• 向集合内插入 $x$；
• 删除集合内的 $x$。

每次操作后要求输出 $\max\limits_{x,y\in S,x\ne y}{(x+y)\bmod C}$（或报告 $|S|< 2$），其中 $C$ 为定值。

$n\le 5\times 10^5$，值域 $[0,1073741823]$，ML 128MB，强制在线。

link: https://www.luogu.com.cn/problem/P6105

思路

先将每个数都对 $C$ 取模，那么 $x+y\in[0,2C-2]$。

$x,y< \dfrac C2$ 的情况是平凡的，考虑直接用 std::set 维护所有小于 $\dfrac C2$ 的数，取最大、次大值计算即可；

$x+y\ge C$ 的情况也非常好维护，直接找 $S$ 的最大值、次大值计算即可。

剩下的情况是 $x< \dfrac C2\le y< C-x$ 的情况。欲最大化 $x+y$，只需最小化 $(C-y)-x$（但不能小于 $0$）。

分开维护 $< \dfrac C2$ 的数集 $A$ 和 $\ge\dfrac C2$ 的数集 $B$，维护 $A$ 的每个数在 $B$ 的后继，$B$ 的每个数在 $A$ 的前驱。

但是这样每次操作涉及的修改是 $O(n)$ 的，不够优秀。

考虑优化：每个 $A$ 中的数 $u$ 如果记录后继 $v$，那么 $[u,v)$ 间是不存在 $A$ 中的数的，否则 $u\to v$ 一定不是目前的解。我们用 std::unordered_map 维护每个点的后继/前驱（只维护有可能是解的），单次操作涉及修改是 $O(1)$ 的。

时间复杂度 $O(n\log n)$，常数非常大。

代码

https://www.luogu.com.cn/record/76109270（67 分代码，未卡常）