LCA 树上倍增法 实质是把节点每次向上暴力移动一步变成更加高明的按 步向上移动，借用的是每个数都可进行二进制分解的定理。期间维护一个父节点数组 fa，fa[i][k] 代表 向上移动 步的父节点。那我们该如何更新这个父节点呢？显然有 ，就是两次向上移动 步，因此可以用 fa[fa[i][k - 1]][k - 1] 来递归更新。 初始化时使用宽搜，把所有点的深度更新一遍。注意要设置...

小星野战力那么强一个人一组就够了ᕕ(◠ڼ◠)ᕗ 您已获得最佳的阅读体验！以及上面的小彩蛋…… 我们会发现这道题和 P5785 任务安排 长得神似。两道题都是把一个连续的序列分成若干块（块数没有特殊限制）。这启发我们把状态设置为 dp[i]，含义是：“把前 个士兵全部分好的最大修正战斗力”。 现在我们着手设计一个暴力 DP 程序，分析如下图： 因为 部分已知，就是我们的 dp[j]；我...

受限于在线编辑器的性能瓶颈（省流：写太多了会很卡），在此决定把另外的（不在算法提高课中）DP斜率优化题目单独拎出来写一篇做题笔记。旨在记录算式消元换元的原则与技巧、凸包维护的方法。题目大致由易到难。 洛谷 P3195 [HNOI2008] 玩具装箱 题目地址：P3195 题目难度：省选/NOI- P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进...

前情提要：Day1 单调队列优化 斜率优化 引 洛谷 P2365 任务安排 题目地址：P2365 题目难度：提高+/省选- 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 个任务被分成若干批，每批包含相邻的若干任务。 从零时刻开始，这些任务被分批加工，第 个任务单独完成所需的时间为 。在每批任务开始前，机器需要启动时间 ，而完成这批任务所需的时间是各个任务需要时间的总和（...

有人私信我，说能不能不要在博客里写那么多“显然”。我的回答是：“好的，全部换成‘Apparently’”。我寻思我也没写那么多显然啊 单调队列优化 简介 我们都知道单调队列是用来 维护一个序列的单调性的，在一个定长区间内，单调队列可以做到输出当前扫描区间内的最值元素。通过维护区间最值，在动态规划问题中，可以有效节省状态枚举带来的效率浪费，有时还可以用来对数组降维，是非常实用且简单的优化方法...

并查集 并查集，或称DSUDisjoint Set Union，是一种管理元素所属集合的数据结构。每次查询时把沿途的节点的父节点一并设置成全局父节点，从而达到均摊复杂度 的超高效率（其中 为 的反阿克曼函数，可以看作为常数复杂度）。基于并查集的许多特性（包括好写），人们开发出了许多不同种类不同用途的并查集，其中就包括带边权的权值并查集和对元素进行分类的种类并查集。这篇文章将探讨这两种并...

单调栈/单调队列 单调栈 单调栈Monotone Stack，顾名思义，是一种栈状结构，且栈内元素单调。它既满足栈的“先进后出F I L O”性质，也符合元素从栈顶到栈底呈单调排列（或者从栈底到栈顶）。根据单调性的不同，大致可以分为“单调递增栈”和“单调递减栈”。若无特殊说明，单调栈的递增/递减判断顺序是从栈顶到栈底。 在单调栈构建过程中，有如下要求： 当前待插入元素与栈顶元素满足全栈的单...

上回书说到：平衡树。 伸展树简介An Indroduction to Splay 由 和 于 年提出的一种数据结构。后者证明了路径压缩的并查集的时间复杂度、求解 强连通分量的其中一种方法也以他的名字命名。 是一种二叉搜索树，与平衡树类似，它也可以通过“旋转”进行自我平衡。通过“伸展操作Splay”来将某个节点旋转至根节点来满足二叉搜索树的性质。能够在均摊 的时间复杂度内完成节点的...

书接上回：二叉搜索树 BST。二叉搜索树是本文所讲平衡树的必要前置知识。 平衡树简介Brief Introduction of Treap 平衡树是为了解决普通二叉搜索树（）时间复杂度退化现象而产生的一种复杂度更为稳定的数据结构（但它仍然属于 的一个子类，因此具备 的所有性质）。在极端的数据面前（具备单调性的数据）， 会退化成为一个 的算法。但是通过引入随机化参数，在数学期望的控制下就...

二叉搜索树简介A Brief Introduction 二叉搜索树Binary Search Tree是一种特殊的二叉树，它有如下的性质： 左儿子（如果存在）的节点值比当前节点的值要小 右儿子（如果存在）的节点值比当前节点的值更大 某个节点的左/右子树（如果存在）也为一个二叉搜索树 中序遍历得到的节点值序列是不下降的（属于是推论） 二叉搜索树是很多重要树形数据结构的理论基础，例如树堆Tr...