数据结构学习笔记
Black_Porridge · · 个人记录
和 数据结构做题记录 一起食用更佳～
可持久化
- 可持久化：保留且支持访问每一个历史版本，允许修改部分（全部）历史版本。
（放一个典中典）
-
可持久化数组：我们暴力的想到把数组的每一个历史版本存下来，但是显然这玩意儿是
n^2 量级的。注意到每一个历史版本只会修改一个数，不难想到在下标线段树中每次只会修改一条链，即\log n 个节点。所以我们只需要新建这一条链，再和前一版本的线段树关联起来就可以了。每次查询则直接从对应版本的根节点开始查询就可以了。时间复杂度O(n \log n) ，空间也是O(n \log n) 的。 -
可持久化线段树（主席树）：原理和上面的内容相似，这里主要写主席树的适用情景。一般我们对于一个序列上的、查询可减的操作的问题做主席树。比如 园丁的烦恼 这道题目：给出若干个点，多次询问给定矩形内有多少个点。这是典型的二维数点问题，且不强制在线，自然可以用 cdq分治/扫描线等离线做法解决，我们考虑使用主席树在线解决。将每一列点看成一颗线段树的不同历史版本，对于每次询问
(x1,y1,x2,y2) ，查询y2 版本的sum(x1,x2) 和y1-1 版本的sum(x1,x2) 并将二者相减即可。 -
可持久化01trie：板子题
第一步先将
a[p] \oplus a[p+1] \oplus ... \oplus a[n] \oplus x 转化为sum[p-1] \oplus sum[n] \oplus x ，对于每次询问，我们用正常套路在 Trie树上贪心取反即可。但是每次询问还有p \in[l,r] 的限制，显然r 这个限制是好解决的，我们考虑可持久化Trie树，在第r 个版本上查询；而对于l ，我们记录Trie树上每一前缀所对应的序列中的版本最大值即可。
习题
1. P4648 [IOI2007] pairs 动物对数
分类题真难写啊！！考虑对于
-
将下标排序后用滑动窗口计算答案。复杂度 $O(n \log n) -
发现曼哈顿距离这个限制会框出一个菱形，不好做，于是考虑将其转化为切比雪夫距离（$\max(|x_a-x_b|, |y_a-y_b|)$。我们将曼哈顿距离的公式展开： $dis(a, b)=max\{ x_a- x_b+y_a-y_b, x_b-x_a+y_a-y_b,x_a- x_b+y_b-y_a,x_b- x_a+y_b-y_a\} 它等价于
max\{|x_a- x_b+y_a-y_b|, |x_a- x_b+y_b-y_a|\} 。不难发现当a'=(x_a+y_a,x_a-y_a), b'=(x_b+y_b,x_b-y_b) 时，原式为两点之间的切比雪夫距离。在曼哈顿距离被转化为切比雪夫距离之后，距离的限制变成了一个矩形，也就是我们熟悉的二维数点问题，用树状数组/主席树即可解决。复杂度
O(n \log n) 。 -
我们套路地枚举第一维，将剩下两位的曼哈顿距离转化为切比雪夫距离，根据前缀和进行三维数点即可。
点分治
cdq分治
- 是一种以
\log q 的时间为代价，将动态问题转化为若干静态子问题的离线求解思想。一般可以使用cdq分治的问题需要满足可离线、修改对查询的影响可叠加。
习题
1.P4390 [BOI2007] Mokia 摩基亚
静态版本是典中典二维数点（扫描线+树状数组+拆贡献）。该问题是存在时间轴的动态版本，利用cdq分治将时间分治，横坐标归并排序，纵坐标树状数组即可解决该问题。时间复杂度
2.P3810 【模板】三维偏序（陌上花开)
和前一题几乎没有差别，