受限于在线编辑器的性能瓶颈（省流：写太多了会很卡），在此决定把另外的（不在算法提高课中）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...

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

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