讲师：杨宁远，NOI2022Au，rk20，from 成都七中
DS
list
auto 定义指针。
*i 访问元素。
prev(i) next(i) 访问前驱、后继的值。
rbrgen rend 含义相反。
front back 放回头元素和尾元素。
insert(iterator,value)，会在迭代器前插入元素。
erase(iterator)，删除元素。
a.swap(b)：O(1)
merge 把两个有序的 list 合并。a.merge(b)
vector
a.resize(n)，强制把 a 的大小变成 \(n\)。往后加 \(0\)。
原理：倍增数组
删除元素空间不会变小。
shrink_to_fit 强制把空间变为 fit ，O(元素个数)
支持随机类型访问
insert erase O(后面元素个数)
a.swap(b) O(1)
set
要求给定元素可以比较
结构体内自定义排序
bool operator <(const node &x)const{
}
erase(值或迭代器)
find(值) 返回迭代器 不存在——set.end()
count(值) 返回0/1
lower_bound upper_bound 返回迭代器
复杂度 \(O(\log)\)。
multiset
count(值) 复杂度 O(log+元素个数)。
unordered_set
C++11 哈希实现
无序 复杂度 O(1)
map/unordered_map
访问空下标会创建元素 应该用 mp.find(x)==mp.end()) 进行判断
lower_bound upper_bound 返回迭代器
queue
空间常数大。
a.swap(b) O(1)
deque
时空常数巨大
底层实现用两个 vector 拼接起来
存在 shrink_to_fit
支持下标访问
建议用 list 或自己实现 deque
priority_queue
本质是二叉堆，实现是 vector
加入删除复杂度 \(O(\log)\)，常数小。类似 BIT。
ST表与RMQ
\(f_{i,k}=min(a_{i\sim i+2^k-1})\)
递推：\(f_{i,k}=min(f_{i,k-1},f_{i+2^{k-1},k-1)\)
询问：\(min(f_{l,k},f_{r-2^k+1,k-1})\)
可以用于区间线性基。
__lg(x) 返回 \(\leftfloor \log x\rightfloor\)。
倍增求LCA
\(p_{u,k}\) 表示 \(u\) 往上跳 \(2^k\) 步到哪。
\(p_{u,k}=p_{p_{u,k-1},k-1}\)
把较深的跳到同一高度。
注意判断跳完以后是不是一个点。
只要不会相遇就一直跳。
最后多跳一步。
RMQ求LCA
记录 dfs 序（可重）。
记录每个节点的 dfn
两个节点的 LCA 一定在欧拉序中两点 dfn 中间一段区间，是深度最小的。
用 ST 表解决（深度最小 \(\rightarrow\) RMQ）。
预处理 \(O(n\log n)\) 询问 \(O(1)\)
四毛子求LCA
+1-1RMQ
分块，分 \(\log n/2\) 块。
可以发现，欧拉序相邻的深度差为 \(1\)，利用四毛子。
\(O(n)\) 预处理，\(O(1)\) 查询。
笛卡尔树
不断找最小值，把区间分裂，划分左右子树。
增量法规建笛卡尔树。
假设求出了 $1\sim i $ 的笛卡尔树，可以发现，\(i\) 号点一定在最靠右的链上，且一定没有右儿子，根据定义，这是显然的。
不可能是某个时刻走左儿子得到的。
建树
如果 \(i+1\) 号比 \(i\) 号大，右儿子。
如果小，往上跳，直到跳到某个点比 \(i+1\) 号大。
对于这个点，令 \(i+1\) 号为它的右儿子，原来的儿子链为 \(i+1\) 号的左儿子。
均摊线性。
性质：lca为区间最值。
构建的本质：维护右链。
四毛子求RMQ？
upd:
二叉堆
insert：向上更新。
erase：将根节点与数组最后一个叶子节点交换后向下调整。
应用：排序 动态维护最值
中位数
用两个堆 small large
不断维护大小平衡
始终尽量维护 small.size()<=large.size()<=small.size()+1
序列合并
二分做法:二分前 \(N\) 小的数中最大的一个，发现对于 \(a_i\) ,合法的 \(j\) 单调不降，双指针做。
堆：对每一个 \(a_i\) 加上 \(b_1\) 后放入堆里，对于最优的求出后继状态（把 \(b_j\) 向右扩展），放入堆里。
左偏树
特殊的二叉堆。
dist:从一点走右链能走多少步
左儿子的 dist 大于右儿子的 dist 。
右链是 \(\log\) 级别。
类似完全二叉树向左偏，而完全二叉树的右链是 \(\log\) 的。
启发式合并
将 \(n\) 个堆合并，复杂度是 \(O(n\log^2 n)\)。
左偏树的合并是严格 \(\log\) 的。
int merge(int x,int y){
if(!x | !y) return x | y;
if(val(x) > val(y)) swap(x, y);
r(x) = merge(r(x), y);
if(dst(l(x)) < dst(r(x))) swap(l(x), r(x));//保证满足左偏树的性质
dst(x) = dst(r(x)) + 1;
return x;
}
不会左偏树。
从归并排序的角度考虑合并
罗马游戏
对每个人用并查集维护在哪个团，用左偏树维护团。
删除堆顶元素：合并左子树、右子树，标记死亡。
Monkey King
通过此题观察左偏树类题的特征：往往类似于并查集，但一般会查询并查集内最值，并对最值有所更改，这是并查集无法维护的，所以会采用左偏树维护。
标签：log,迭代,复杂度,元素,day2,swap,2.3,ds,左偏 From： https://www.cnblogs.com/BYR-KKK/p/18004463