数据结构杂谈
ty_mxzhn
·
·
算法·理论
插入标记回收算法
本算法在 lxl 讲课时提出。然后立马就被放到了数据结构专场的签到题。
解决的问题是：
第 $i$ 种操作是 $x\leftarrow F_i(x)$ 这样。可以离线。
算法流程如下：
1. 插入数据。在 $l$ 时间开始前把 $x$ 加入集合 $S$ 中。
2. 标记。在 $i$ 时间执行 $S\leftarrow F_i(S)$。
3. 回收数据。在 $r+1$ 时间开始前把 $l$ 丢进去的数据从 $S$ 中回收。
难得 lxl 讲这么简单的算法。
## 例题 $1
PKUSC 的题（澡堂）：F_i(x)=x+[x\in[l_i,r_i]]。
显然 S 中节点保持单调顺序。直接用线段树二分定位线段树区间加即可。时间复杂度 O(n\log n)。
平衡树合并技巧
平衡树合并是在没有一些奇怪操作的 FHQ-Treap 上的合并两颗不需要满足任何条件的 FHQ-Treap 的方法。
一个暴力
假设我们要从 y 合并到 x，启发式后直接一个一个合并。
然而这样复杂度是错的，因为我们可以不断分裂合并。
一个暴力？
直接按照 x 的键值分裂 y。然后把 y 的两边放到 x 的两边递归合并。
需要注意的是要求 P_x>P_y 也就是按照优先级决定谁合并谁。其实理论上按照大小合并会更优但是其实差不多。
复杂度证明
假设 n,q 同阶。上述“暴力”的时间复杂度为 O(n\log n\log V)。
证明考虑设计势能函数 \epsilon(x) 表示 x 内部相邻两点的值域差对数的和。
设值域连续段有 c 个，这里的连续段指的是合并 A,B 两颗平衡时后新树的值总是成 A..B..A..B..A..B..A..B.. 这样。则 c=8。
合并时有值域连续段内总有 O(c) 个节点的势能减少 1。而上述“暴力”的复杂度最高只有 O(c\log n)。
显然分裂不增加势能。
友情提示
例题 2
例题：Ynoi TEST_100。
用刚才两个算法。则相当于对 a_i 的大小关系分讨后使用平衡树合并在一起。
并不是这样的，因为强制在线限制了第一个算法。
考虑分块。因为值域很小所以我们可以每一段内暴力平衡树合并跑出 1\sim V 的答案。
查询时散块暴力，跳整块直接用刚才平衡树合并时跑出来的结果即可。
## 例题 $3
例题：Splitting Haybals P。
用刚才提到的两个算法。插入标记回收以后，按照 0 分裂以后分别打加法标记并合并。
# 标记永久化技巧
## 引入
树套树的矩阵修改无法 pushup，也不能简单 pushdown。
此时我们需要标记永久化。用来更好的**计算修改与查询**的贡献。
## 修改与查询
先考虑第一层线段树。修改时会对一些区间的子树产生贡献，然而这些区间的祖先也会有一定的贡献。
此时为了方便考虑这两者的组合，我们引入标记永久化技巧。
## 例题 $4
题目描述：矩形加矩形和。
在第一层线段树上，每一个分裂出来的区间的祖先在第二层线段树上加。
在第一层线段树上，维护第二类第二层线段树维护每一个分裂出来的区间的标记永久化。这个标记永久化是在第二类第二层线段树中的。
查询的时候把路上每一个第二类第二层线段树查一遍。
例题 5
咕咕咕，本专栏持续更新。
抽象为二维问题
lxl 课件里的一部分吧。这里稍微提一下。
例题 6
题意：给你 n 个区间，每次查询给一个区间 [l,r] 求所有包含 [l,r] 的区间的交。n,q\le 10^5。
将区间 [l,r] 抽象为二维平面中的一个点 (l,r)。
查询时相当于求 a\le l,r\le b 最小的 a 和最大的 b。
在平面上是求一个点右下方的边界点。考虑扫描线，用一个树状数组维护。O(n\log n)。
例题 7
题意：每次询问时，临时将 [l,r] 加上 1 后求种类数。n,q\le 10^5。
扫描线。记录目前每种类的数的第一次出现和目前最后一次出现的数量，每次只有 O(1) 个位置有修改。
当一个区间内包含了所有的 a，并且不包含 a-1，这个数列会失去 a。
当整个数列内没有 a，并且这个区间里包含至少一个 a-1，这个数列会获得 a。
每次失去 a 和获得 a 的 l，位置都是一个区间。贡献可以直接叠加。
使用树状数组维护。