《树状数组》一节习题笔记(一)
本文记录了作者学习罗勇军《算法竞赛》中《高级数据结构》一章《树状数组》一节时,完成部分习题的笔记。
POJ 2299 - Ultra-QuickSort
题意
给定一个序列。可以执行若干次如下操作:不断交换相邻的两个元素。求至少需要多少次交换操作才能使得序列变得有序。
思路
题目要求交换操作的次数。有如下性质:一个序列的逆序对数就是通过相邻交换使它变成有序序列的最少次数。如此,本题实际上是求序列中逆序对的个数。用归并排序和树状数组都可解。
POJ 2481 - Cows
题意
有 N 个区间 [S_i, E_i] 以 1 \sim N 编号。定义两个区间 i 和 j 满足 S_i \leq S_j \land E_j \leq E_i \land E_i - S_i > E_j - S_j,则称区间 i 比区间 j 更强。对于每个区间,求出比这个区间强的区间的个数。
思路
依据题目中给出的定义,当 [S_j, E_j] \subsetneqq [S_i, E_i] 时,i 比 j 更强。将所有区间 [S, E] 映射成二维平面上的点 (S, E),那么 i 比 j 强就等价于点 i 在点 j 的左上方。这就成为一个二维偏序问题。
将所有区间按照如下方式排序:按 S 升序排序;若 S 相同,按 E 降序排序。从左往右扫,扫到第 i 个时,S 天然有序,我们只需要判断 E 的大小,可以用树状数组统计前 i-1 个区间中 E 值大于等于 E_i 的区间个数。特别地,如果两个区间完全重合,可以直接继承此前的答案,无需重复计算。用 ans 数组记录离线下来的答案,最后统一输出即可。
POJ 1195 - Mobile phones
二维树状数组模板。
POJ 3321 - Apple Tree
题意
有一棵有 N 个节点的树,树的根节点是 1。每个点的权值要么是 1,要么是 0。初始时节点权值都为 1。有 M 次操作。有如下两种操作:
C x表示点 x 的权值发生变化:如果当前权值是 1,变为 0;如果当前权值是 0,变为 1。Q x表示查询以 x 为根的子树的权值之和。
处理这些操作。
思路
可以通过 DFS 将树转化成一个序列,任意一个子树在这个序列上都是连续的,记录每个子树对应序列的起始和结束位置。之后用树状数组维护序列即可。
注意:由于 POJ 没有 O2 优化,本题使用 vector 存图可能会超时,建议使用链式前向星存图。
POJ 3264 - Balanced Lineup
本题同洛谷 P2880。
题意
给定一个长度为 N 的序列 A。有 Q 次询问,每次询问包含两个整数 l 和 r,代表询问序列中下标区间 [l, r] 的最大值和最小值之差。
思路
参考题解:洛谷 P2880 题解 - stone_juice 石汁
这题可以用 ST 表解决,比较简单。我们这里用树状数组解决。
维护两个树状数组,一个记录最大值,一个记录最小值。单点修改和一般的前缀和树状数组比较类似。下面着重介绍如何实现查询。
最大值没有可减性,因此不能像前缀和树状数组那样直接统计前缀。我们可以用递归的思想解决。要查询区间 [x, y] 的最值,若 x = y,直接返回 A_x;否则,即 x < y,可以大致分为两种情况:
- 当 y - \operatorname{lowbit}(y) \geq x 时:此时可以将区间分为两部分:[x, y - \operatorname{lowbit}(y)] 和 [y - \operatorname{lowbit}(y) + 1, y]。不难发现后半部分就是树状数组中的 T_y,而前半部分可以递归求解,然后取最值即可。
- 当 y - \operatorname{lowbit}(y) < x 时:此时不能直接越过 \operatorname{lowbit}(y) 的长度了。可以逐个处理,将区间分为 [x, y-1] 和 y 两部分。后半部分可以直接取 A_y,前半部分依然可以递归求解,然后取最值即可。
这样,我们就完成了树状数组维护区间最大值的操作。
POJ 3368 - Frequent values
题意
给定一个长度为 n 的非递减序列,有 q 次询问,每次询问包含两个整数 i 和 j,输出下标区间 [i, j] 中出现次数最多的数的出现次数。
思路
本题也可以用 ST 表解决,比较简单。这里使用树状数组解决。由于序列非递减,相同的数在序列中总是连续出现的,因此可以将序列压缩成一组一组的数,相同的数放到一组,权值为出现次数,并记录每个下标对应的组的编号和每组的左右端点。随后和上题一样维护一个区间最大值树状数组。
查询时,分为三种情况:
- i 和 j 在同一组中:只出现一种数。直接输出 j - i + 1。
- i 和 j 在相邻组中:出现两种数,但都不完整(这里是通俗表述,实际上有可能完整)。通过每组的左右端点计算两组分别被选入区间 [i, j] 的长度,取较大值输出即可。
- i 和 j 不在同一组也不再相邻组中:这意味着中间至少有一个完整的组。最大值有可能是:i 所在组被选入区间的长度、j 所在组被选入区间的长度、中间组长度的最大值。前两个求法和第二种情况一致,而第三个可以用树状数组维护求解,取最大值输出即可。

