数据结构

未分类

考点

基础：

• 数组，链表
• 队列，栈
• 堆（priority_queue）
• 并查集

略复杂的：

• 树状数组/线段树二选一
  

  《not only success 线段树完全版》
  hdu炸了，请上http://acm.split.hdu.edu.cn/

• 树（存树）
• 树上LCA
• DFS序列、括号序列

更复杂的：

• 启发式合并
• 单调队列
• 前缀和
• 二分
• 分治

不需要掌握的

• 点分治
• 分块
• 莫队
• 主席树
• 平衡树

倍增LCA

找到最深的祖先
开一个数组f[i][j]
表示从i走$2^j$步可以到达祖先
从而使枚举达到log级别

DFS序列与括号序列

并不是所有结构都可以表示成线段的结构，比如一棵树，并不能用线段树直接维护。这两个序列可以将树上问题转换为线性的，从而用线性数据结构维护。

DFS序列（类似前序遍历）

我们使用dfs序列将一棵树排成一个序列。
对树进行dfs，如图1

对子树的整体修改就可以转化为新的序列上的区间操作，这就可以将树转化为线性结构。

括号序列

如图二，DFS过程中，1处记录一个+1符号，2处记录+2，4记录+4，之后无法继续进行DFS，记录-4，回溯。回到2，记录+5、-5...继续进行直到完成，结果：
+1 +2 +4 -4 +5 -5 -2 +3 +6 -6 +7 -7 +8 -8 -3 -1
将+看做（，-看做），形成一个合法的括号序列。
来考虑链。
例如链1->6，由1 3 6构成，那么括号序列上从1到6所有不在该链上的东西都会被消掉。留下的就是路径。这一性质只能用在无转弯、自上而下的链上。
而对于任意链，先求LCA，再使用即可。

启发式合并

有n堆东西，每次操作将两堆合并为一堆，维护合并过程。
可以使用并查集。
暴力时我们直接加入，复杂度$O(n^2)$，而启发式合并的区别就在于优先选择小的一堆，复杂度O(nlogn)，这是因为小堆次数至少会扩大2倍，因此最多会被合并logn次，这样总复杂度为O(nlogn)
没什么专门的题，总之就是个神奇的玄学优化，yy一下就出来了

单调队列

定义

以1 3 2 4为例
加入1 1
加入3 1 3
加入2 1 2
加入4 1 2 4
不断删队尾直到保持单调性

应用：滑动窗口（LuoguP1886）

（几乎是唯一应用，有变式）
给出n个数，再给出一个k，有很多长度为k的子区间，求出这些区间的最小值。
暴力：扫一下，$O((N-k+1)*k)$
线段树：区间询问最小值，log询问，$O((N-k+1)*logn)$
单调队列：
考虑如何求第一个区间的答案，对于单调递增的单调队列，第一个元素就是区间最小值。
对于区间[2,k+1]与[1,k]，区别只有a[1]与a[k+1].加一个数直接插进去即可，而如果第一个数是最小值那么就是队首，而如果第一个数不是最小值这个数就必定已经被删掉了，否则就无法维护单调队列的单调性。这样转移就是O(1)的，总复杂度O(n)

分治

参考MergeSort

例题

T -5 平均值最大子区间

最大的数
不要思维江化.jpg

T -4 区间最小值乘区间长度最大

如果包含最小的数，那么要求的最大值就是整个区间长度与该数的乘积，因为这样比较大。
如果不包含这个数，那么这里考虑的两个区间就是左右两个区间。
这样就分治为左边与右边两个问题，用线段树维护区间最小值即可。
复杂度$O(nlogn)$,这就是著名的笛卡尔树。
【思考题：如何O(n)】

T -3 区间端点最小值乘区间长度最大

这个与刚才不同对另一部分是有影响的，因此不能分治。
假设对点i，作为某一区间的左端点，我们希望右边的点比它大，那么我们就希望找出最靠右的比它大的数，这时可以解决这个问题。
这里我们可以二分一个长度代表后面l个数中有没有更大的。因此这里维护一个后缀最大值，O(1)的询问后l个数的最大值。
然后用这个结果更新答案即可。
线性做法证明很复杂，并不能证明，“两头砍最小的不断砍就行”

T -2 求出子区间中位数

$O(n^2logn):$
用两个数，一个存比中位数小的，一个存比中位数大的
加一个小数会使中位数变大，因此将一个数扔到大根堆里，另一个同理。
$O(n^2):$
枚举L，将R从右往左移，将一个一个加变成一个一个删除
排序一下，用一个链表维护从小到大的顺序，那么中位数就是中间位置的数。
删除O(1)，删掉的数比中位数小则向后移动，否则向前移动，即转移也是O(1)的。

T -1 一个点阵有些特殊点，一个点的安全性就是到这些点的曼哈顿距离的最小值，要求求一条(1,1)到(n,n)的路径使安全性的最小值最大

(LuoguP1514)

见最大化最小值先想二分

$O(n^2logn)$
假设现在二分结果为k，那么离特殊点曼哈顿距离<=k的点（将所有特殊点加入队列中BFS）全部标记为不能走，然后BFS判断是否联通。
$O(n^2)$
如果只有一个特殊点，按曼哈顿距离倒序枚举距离为k的点。当距离为k时连通，那么k就是所求的值。
而如果有多个特殊点，倒着搞一下BFS的队列就是曼哈顿距离最大的。
如何判断是否连通呢？用并查集维护，每加入一个就扔到集合中。

T0 对序列A,B，求一个最大子区间[L,R]满足A区间[L,R]的和除以B区间[L,R]最大（实数除法）

暴力：预处理前缀和，枚举左右端点$O(n^2)$
假设结果为[L,R]，那么A[L,R]/B[L,R]=x
如果现在的答案是m，check就是是否存在一个区间使得x>=m
那么该问题等价于判断A[L,R]-m·B[L,R]>=0
定义C[i]=A[i]-m·B[i]，则问题为是否存在C[L,R]>=0
即是否存在C[i]>=0，然后回推，这就是在求A[i]-mB[i]>=0，也就是求A[i]/B[i]的最大值。

*对于实数上的二分，直接限定二分次数就行了，如30或50

当然并不是每个题都可以这样玄学的化简.

像这样求f(x)/g(x)最值的这类问题叫分数规划问题，一般二分答案

check函数一般列式化简，可以转化为一个比较简单的式子。
R可以任意设，稍大点就行
又如：假设每个边的权值有a,b，求一条路径使得$\sum \dfrac{A_i}{B_i}$最小

T12 给一棵大小为N的树，要求维护：1）换根 2）修改点权 3）查询子树最小值，N<=100000（BZOJ3306）

如果没有换根，DFS序+线段树硬搞

只有一部分的dfs序会改变
定一条从原父亲变成新父亲路径，如果不在这条路径上的点子树是不会改变的，直接询问。
否则，对于一个节点来说，儿子变父亲的伦理悲剧，使得唯一不是子树的只有从新根来的方向。由于儿子的dfs是个区间，这段区间就被去掉了。
假定原先区间为[p,q]，儿子为[L,R]，那么我们实际上就是询问[p,L-1]与[R+1,q]这两个区间，复杂度仍然是$O(nlogn)$

T13 N个点的树，每个点点权v[i]。给q次询问，每次询问从p1到p2的路径上能不能找到三个点点权使之能组成三角形三边。（所有点的点权不超过int）

暴力：$O(n^4)$枚举
观察a+b>c，这是能组成三角形的条件。
因此a+b<=c不能组成，而a+b=c就是肥不辣鸡数列
由于该数列在45项后会爆int，而极限情况下46个点没有三角形就会爆int
也就是说，两个点之间不能超过45个结点。
因此当结果超过45就直接输出Y，否则暴力一下，这个复杂度是可以接受的。

钟神的建议

• 提高代码能力

  写对暴力分
  比如三分钟写出来线段树
  多写搜索题或者模拟题

• 对拍

• 调试能力

  看着调试
  Dev的调试
  gdb调试