RMQ
ST 表
不用讲，浅显易懂，背背板子。
例题
Loj 10121 与众不同
一个需要瞪眼发现单调性的题目。
- 分析
1.维护 \(last_{val}\) 表示元素 \(val\) 上一次出现的位置
2.维护 \(s_i\) 表示以 \(i\) 为右端点的完美序列的起点，则：
\[s_i = \max \left \{ s_{i - 1}, last_{a_i} + 1 \right \} \]如果这样去维护 \(s\) 的话就使得 \(s\) 一定是单调不减的。
3.对于询问的 \([l,r]\) 存在一个分界点 \(p\) 使得终点 \(p\) 在 \([p,r]\) 间的完美序列的起点也在 \([l,r]\) 内，终点在 \([l,p - 1]\) 间的完美序列起点在 \(l\) 左边
4.\(p - 1\) 之前的起点都是 \(l\)，则完美序列的最大长度为 \((p - 1) - l + 1 = p - l\)，若起点在 \([p,r]\) 间则用 st 表维护 \(i - s_i + 1\) 的最大值，则每组询问的答案为：
\[\max \left \{ p - l, \max_{i \in [p,r]} \left \{ i - s_i + 1 \right \} \right \} \]5.由于 \(s\) 单调不减，所以 \(p\) 可以二分查找得到
6.注意 \(a_i\) 的值域可能为负，\(p\) 可能不存在
时间复杂度 \(O(n \log n + m \log n)\)。
树上倍增
通常维护 \(dp_{i,j}\) 表示节点 \(i\) 沿着祖先跳 \(2^j\) 到达的节点编号、区间最值、区间和等。
LCA
什么啥比倍增，我爱树剖。
平心而论还是倍增好写。
性质
1.LCA 与根是谁有关
2.树上两点距离与根无关
3.设 \(dis_i\) 表示根到 \(i\) 的距离，\(dist(i, j)\) 表示树上节点 \(i,j\) 间的距离，则：
\[dist(x, y) = dis_x + dis_y + 2dis_{LCA(x, y)} \]容斥原理。
例题
P3398 仓鼠找 sugar
推 LCA 性质。
- 题意
给定一棵树，\(q\) 次询问，每次询问 \(a\) 到 \(b\) 和 \(c\) 到 \(d\) 的路径是否有交。
- 分析
用二元组 \((x, y)\) 表示 \(x \to y\) 这条路径
可以大胆猜一个结论：两段路径有且仅有其端点的 LCA 与另一个路径有交。
证明：
若有两个交点，那么原图为一棵基环树，存在环，与原条件矛盾。
P4281 [AHOI2008] 紧急集合 / 聚会
- 分析
1.三点可以先取两点的 LCA 再与第三点求 LCA
2.可以证明三点至多只会有两个不同的 LCA
3.容斥算得三点间的距离：
\[dis_x + dis_y + dis_z - dis_{LCA_{x, y}} - dis_{LCA_{y, z}} - dis_{LCA_{x, z}} \]CF379F New Year Tree
- 分析
1.每次操作只会加同一深度、同一子树内的两个节点，树的直径至多加一且如果直径增加，一定是新加的节点导致的，也就是说新加的节点一定是直径的端点，且两个新加的节点是等价的
2.维护直径的端点，比较 \(dis(cnt,x), dis(cnt,y), dis(x, y)\)，其中 \(x, y\) 为直径端点，\(cnt\) 为新加节点
3.倘若用倍增去求 LCA 每次单独更新 \(fa_{cnt,i}\) 即可
时间复杂度是小常数 \(O(q \log q)\)。
标签：cnt,端点,LCA,倍增,节点,dis From： https://www.cnblogs.com/endswitch/p/18375722