祝馀宫

文章总览：百脉甘津宁神久李超线段树，是一种维护带斜率的线段信息的线段树，早就听说了，所以今天跑过来填坑了。李超线段树也是属于线段树的变种，主要的应用也就是刚刚说的维护带斜率线段。并且因为他能维护这种特殊的几何结构，也可以用来编写斜率优化DP，所以说也算是比较重要的数据结构了。 下为本文大纲： 李超线段树推导 李超线段树模板 李超树应用基础 李超数应用斜优 算法推导：壶中洞天云螭眠 李超线段树推导 主要思想：云吟那么刚刚也说了，李超线段树就是一种维护带斜率的线段的线段树，一般来说查询的都是在一条垂直于 $x$ 轴的是线上我们插入的线段与其的交点中最顶端（纵坐标最大）的那一个。 很显然，我们对于每一个节点，只需要存储我们查询的时候的答案（我们将其称之为优势线段）即可。现在的问题是如何快速处理这个所谓的优势线段。 不难想到分类讨论处理插入的情况。如果插入的情况搞定了，查询就是易如反掌。 基础结构：雷音有了大概的思路，我们可以考虑以什么样的载体来存储这个李超线段树。很显然我们面对的是一个非常大的区间，毕竟每个线段的左右端点可以到 $x$ 轴很远很远的地方，那么这种时候我们就只有一种选择： ...

T1 - Farm Tour题目传送门 题目大意现在有 $N$ 个节点，有 $M$ 条边，要从 $1$ 走到 $N$ 然后再回到 $1$。要求走的边不能重复，求最短路径。 解题思路很简单，我们直接把这个图作为网络的一部分，然后另外开一个源点和汇点，发送 2 的流量，走出来的一个最小费用最大流就是我们想要的答案。 正确代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149 ...

文章总览：一心二用之术这个算法其实之前写过，但是写的一塌糊涂，所以说这里重新写了。这篇文章的主要内容是点分治算法，另外会额外拓展一些点分树的内容。点分治很显然就是基于点的分支，其详细内容会在下文介绍，大体分类属于树分治。本文讲述点分治与点分树，树分治就还剩下一个边分治了，接下来是本文大纲： 点分治思想 点分治例题 点分树思想 点分树例题 算法推导：理清逃跑路线那么还是来介绍一下点分治的概念。点分治呢其实是一种基于点在树上的分治，它基于点与树上路径的关系来快速统计一些树上路径的信息。在点分治中，路径可以分为两类： 经过当前根的。这个又可以分为端点为根或者两个端点都不为根。 不经过当前根的。 显然第一类中的第二个情况是可以通过第一个情况造成了两个链拼接而成，而不经过当前根的我们需要接下去递归处理，所以说这里是关于点分治正确性的一些简单证明。 然后我们来思考一个问题，点分治的分治逻辑是什么。因为说一般来讲树都是无根树，我们递归的顺序可以非常明显的影响到我们的复杂度。这个就不难想到是用重心了，因为重心每一次可以排除掉这棵树 $1/2$ 的大小，大大节约了我们的复杂度，这样的话点分治除去 ...

之前是讲过斜率优化DP的，只不过那时候还没有学过计算几何，所以说讲的不是很深，所以说这里来介绍一下如何从几何意义上也就凸包的角度理解斜率优化DP。 友情链接： 【算法介绍】斜率优化优化动态规划 | 祝馀宫 从例题出发题目传送门 题目大意给出 $N$ 个单词，每个单词有个非负权值 $a_i$，现在要将它们分成连续的若干段，每段的代价为此段单词的权值和的平方，还要加一个常数 $M$，即 $(\sum a_i)^2+M$。现在想求出一种最优方案，使得总费用之和最小。 解题思路首先我们进行一个暴力的推导，也就是最原始的转移方程式。 这个不难，我们对于 $i$ 只需要枚举一个断点即可，规定 $j$ 属于上一段的部分： dp[i]=\min_{0\le j\lt i}\{dp[j] + (sum[i]-sum[j])^2 +M\}这个的转移显然是 $O(n^2)$ 的，接下来我们要对其进行优化，那么这就是斜率优化了。首先我们对于这个式子进行一些简单的移项，可以得到下面这个： \begin{aligned} dp[i]&=dp[j] + (sum[i]-sum[j])^2 +M\\ dp[i ...

导数还是太有用了，这下不得不学了。导数的定义就是很简单的，一个函数每一个点上的斜率。这个斜率的求法其实本质上就是一个极限思想，推导也很简单，直接就是用斜率的计算公式即可。 f'(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x) - f(x)}{\Delta x}这篇文章主要是记一写导数的公式和易错点，不然我也容易忘。 特殊函数的导数从最基础的开始。 常数函数常数函数的斜率处处为 $0$，带入上面的公式也可以知道。 幂函数 f(x)=x^a\longrightarrow f'(x)=ax^{a-1}证明： \begin{aligned} f'(x)&=\lim_{\Delta x\rightarrow 0}\frac{(x+\Delta x)^a-x^a}{\Delta x}\\ &=x^a\lim_{\Delta x\rightarrow 0}\frac{(1+\frac{\Delta x}{x})^a-1}{\Delta x}\\ &=x^a\lim_{\Delta x\rightarrow 0}\frac{e^{a\ln(1+ ...

最近在做网络流的题目，接下来说几个我做到感觉有点意思题目。网络流问题其实全是模板，但是难就难在如何把问题抽象成网络流模型。 T1 - 狼抓兔子题目传送门 我是觉得这题的题面很史所以放过来。题目让我们求在能一网打尽的前提下，设置尽可能少的狼。这个所谓的一网打尽，其实是指我们选中一些边以后，不论 $S$ 到 $T$ 怎么走，都必须经过我们选中的边。如果了解了这个，那么就是模板的最小割了（你怎么知道我一开始没看懂在网上查了一圈题解全都是“一眼模板”） T2 - 蜥蜴题目传送门 这题是一道经典的拆点题。因为石柱是有高度的，这个高度相当于是一个限制，所以说我们很容易就可以想到把一个石柱拆为两个点：一个称为石柱的顶端，一个称为石柱的底端。 那么我们可以这样理解题目中的几类操作： 放蜥蜴：建立超级源点 $S$，对于任意有蜥蜴的石柱，建立从 $S$ 到这个石柱顶端容量为 $1$ 的边。容量为 $1$ 是因为这个点只有一只蜥蜴，所以我们放也只能放一只。 石柱：对于每一个有高度的石柱，从石柱顶端连接到石柱底端，容量为高度。这样的话从这个石柱通过的蜥蜴数量就有了限制。 石柱互通：对于任意一对能够互相抵达的 ...

文章总览：高大的背影2-SAT 一开始觉得听玄学的，学了之后有感觉没什么好写，这篇文章简单说一下罢。 SAT 问题的定义 SAT 问题的解法 SAT 问题的例题 SAT 问题的细节 经典模型：紧紧的拥抱 SAT 问题的定义 首先我们了解一下 SAT 问题的定义。SAT 是英文单词适定性（Satisfiability）的简称，一般来说对于 k - 适定性问题，我们都简称为 k-SAT，这篇文章要讲的就是 2-SAT 问题，这是因为当 $k>2$ 的时候 k-SAT 问题是 NPC 问题（但是好像也有解决 k-SAT 的算法）总而言之，这里研究的是 2-SAT 问题。 简单的概括最基础的 2-SAT 的核心，就是对于 $n$ 个二元组。且存在一些形如 $\langle a,b\rangle$ 的矛盾关系，这代表 $a,b$ 不能被同时选中，这里保证 $a,b$ 不属于同一个二元组。问题就是要问存不存在一种方案，使得每一个二元组都选择出一个元素并且不出现矛盾的情况，有时还会让你输出具体的方案，显然方案是不唯一的。 其实这个问题其实并不难看出是可以抽象为图论的，有人的第一直觉就是二 ...

文章总览：雪地的圣女计算几何，好像是非常难的一部分……其实还是数学，说着难，其实也还好（好罢我不会）。总而言之，这篇文章来简单介绍一下最最基础的计算几何，下为本文大纲： 向量的定义 向量的运算 直线表示法 直线的运算 凸包的定义 凸包的运算 半平面定义 半平面模板 几何大模板 几何例题一 几何例题二 前置知识：付记忆入殓 向量的定义 向量的运算 定义：悲鸣，赐死之先声首先定义向量，其实向量在以前的文章也接触过，不过比较基础，而且并没有给出详细的定义，所以说我们还是先说一个较为形式化的定义。 友情链接： 【算法介绍】快速傅里叶变换 - 复数及其运算 | 祝馀宫 向量，顾名思义就是有方向的量，在数学上来说，只要不改变向量的大小和方向，其端点是可以随意再平面中移动的，一般记作 $\vec a$ 。事实上，向量可以认为是一个有向的线段，而有向线段的三要素非常相似于力的三要素，即起点、方向、长度。所谓三要素，就是只要知道了这三个信息，剩下的信息就可以唯一确定，所以我们也用有向线段来表示向量。 除此之外，向量还有一些其他的概念。 向量的模长：就是向量的长度，记作 $|a|$； 零向量： ...

文章总览：一心平衡树是我 114514 年前就说要学的知识点，结果拖到现在……甚至这个封面都是今年春节前就做好了qwq。因为我太菜了，这篇文章主要讲的内容是普通的二叉搜索树和两种 Treap（或许封面得改成 Treap 专题？ 下为本文大纲： 二叉搜索树概念简介 二叉搜索树分段推导 二叉搜索树优劣分析 无旋 Treap 基本概念 无旋 Treap 思想模拟 无旋 Treap 区间操作 无旋 Treap 综合例题 带旋 Treap 思想简介 带旋 Treap 分段实现 带旋 Treap 代码一览 两类 Treap 对比分析 前置知识：二观 二叉搜索树概念简介 二叉搜索树分段推导 二叉搜索树优劣分析 概念讲解：幽府说起二叉搜索树，各位并不陌生，在很久很久以前，我曾写过这样一篇文章： 友情链接： 【算法介绍】笛卡尔树 | 祝馀宫 这里面提到的笛卡尔树，也是二叉搜索树的一种。不过那篇文章并没有详细解释二叉搜索树的详细定义与编码方式，所以说作为平衡树重要的前置知识，我们把二叉搜索树一并在这里讲了。 首先我们来简单介绍一下二叉搜索树的概念。 规定每个节点有一个附加权值。 左子树和右子树 ...

文章总览：盐与犬豪德，失踪多年的我终于回来写文章了（什么？你说我干什么了？你怎么知道我出遐蝶了！），，，言归正传，这篇文章的内容是 CDQ 分治，最近做到了一道关于 CDQ 分治的题目，一看就发现不会，所以这篇文章来讲一下 CDQ 分治的一些基本原理与应用，所谓 CDQ 分治，更广泛的来说是一种思想，它在被提出之前就已经广泛流传于各大巨佬之间，后来被高中的 IOI2008 金牌得主陈丹琦总结，因此而得名。 话说这剧情怎么这么熟悉，上次讲莫队的时候好像和这个剧本完全一样 下为本文大纲： 二维数点问题的规律总结 CDQ分治思想的简单推导 CDQ分治模板题讲解 CDQ分治的简单应用 前情回顾：狮子之尾 友情链接： 【算法介绍】二维数点 | 祝馀宫【算法介绍】扫描线思想 | 祝馀宫 上面这两篇是我曾经结下的关于二维数点的一些文章。我们可以简单的总结一下，从最最开始的一维数点，是如何一步一步拓展到二维数点的呢？ 首先来从一维数点讲起，这应该是数点问题的起源。什么是数点？举个例子，现在我有一个一维的数轴，我往上面标点，标了点以后，查询某一区间，或者某一前缀等等等等有多少个点。这就是一维数点问 ...