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

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

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

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

前言 他只需略微现身，考生瞬间变圆神；只需给他一个不定参，他能把数学题做成英语题；给他一个定值证明，他能逼出考生使用伪证大法。不是含参韦达算不起，而是伪证算法更有性价比。有人说椭圆双曲线简单，新高考I卷丝带线表示不服。对此，五星上将麦克阿瑟评价道：“如果当年美军的考试卷没有圆锥曲线压轴题，美军战士一定能在圣诞节之前回家”。那么，圆锥曲线到底有何魔力？大型纪录片《圆锥曲线传奇》持续为您播出……...

差分约束系统 理论基础 我们称形如下面给出的多元一次不等式组为一个差分约束系统： 它包含 个未知数，以及 个约束条件，每个约束条件是由两个未知数作差构成的不等式。 求解这个不等式组，我们首先考虑移项，例如第一个不等式变成：。联想到最短路的三角不等式，即 ，这个方程组可以转化为一个最短路问题。具体到第一个不等式，就是创建边 ，边权为 。在读入所有不等关系后在建出的图上做最短路即可。 最短...

前言 在写 SPFA 判负环 的时候发现很多题目需要联系到高贵的0/1分数规划，但是截至当时我还没有学这样优雅的算法，故先将 咕一咕，把关于分数规划的东西弄清楚再回去填坑。正好刚考完高一下的合格考，觉得正是适合学新东西的时候，在此归纳一些简单的分数规划知识……这都什么跟什么啊 分数规划基本模型如下： 给出有 个元素的两个数列 和 ，求对整数 ，使得下式最大化： 通俗一点地说，给出...

关于 SPFA，以及…… ……以及它死了，现在有意无意卡 似乎已经成为 OI 出题界的常规操作了…… 算法的流程如下： 遍历 个点 对于当前的点 ，遍历它的所有出边，并获取出边相连的点 进行松弛操作，将 设为 若终点的最短路长度不为正无穷，则找到最短路；否则整张图不连通 但是在第三步中，每个点的最短距离不一定能够被更新——只有上一次松弛成功的点连接的边，才有可能引起下一次更新...

前言 我非常喜欢一些奇技淫巧，每次有机会时就想用点小技巧，既方便了自己、有时还能博来他人的赞叹，实属一举两得的行为。在这篇文章之前，我的奇技淫巧仅局限于高中数学题。接下来我把进入 C++ 编程以来收集的实用小技巧全部放在这里，并不定时更新新的小技巧。希望能帮到后人。 引用伟大的毛主席的一句话： 幸亏古人和外国人替我们造好了这许多符号，使我们开起中药铺来毫不费力。 毛泽东 ——《反对党八股》...

生成树基础 生成树，在 OI 中最多的考法有两种——最小生成树和次小生成树。最小生成树（Minimum Spanning Tree，MST）是最常见的问题，它是原图边权之和最小的生成树（不一定唯一）；而次小生成树，分为严格次小生成树和非严格次小生成树，前者要求次小生成树的权值和严格小于最小生成树的权值和，后者则无此要求，即允许“大于等于”情况的出现。实际考察严格次小生成树较多。 生成树基础算...