前言 Andrew算法可以在\(O(n\logn)\)的时间复杂度通过单调栈分别求出散点的上凸壳和下凸壳，来求出平面上一些点的凸包。 看懂这篇博客，大家需要掌握： 基础计算几何知识 单调栈 本文中的向量恕不加\(\overrightarrow{}\)符号。 凸多边形是指所有内角大小都在\([0,\pi]\)（弧度制）范围内的简单多边形。其他的“凸”请类比理解。 凸包 首先，什么是凸包？ 给你平面上的点集，你需要从中选出最少的点，使得这些点所组成的凸多边形可以包裹住其他所有点。这些点所组成的凸多边形就是凸包。 譬如下面这个点集： 它的凸包是： 下面我将会告诉大家怎么求。 序曲 And...

前言 首先明确，权值线段树是线段树的一个子集。它的思想与线段树一模一样，只是实现的功能更加神奇。 前置知识： 线段树 树状数组 本文将介绍权值线段树、可持久化权值线段树、树状数组套可持久化权值线段树。 权值数组 对于一个序列\(a\)，若它的权值数组\(b\)，则： \[\foralli\in\mathbb{Z},b_i=\sum_{j=1}^{|a|}{[a_j=i]}\] 即\(b_i\)为\(i\)在\(a\)中的出现次数。 我们可以使用线段树来维护权值数组，该线段树便称为权值线段树。 注意\(b\)的大小与值域有关，可能特别大，但中的非\(0\)值分布十分稀疏（最多\(|a...

前言 最小割树（Gomory-HuTree）通过分治的思想，将图中的最小割关系建成一棵带权了树上问题。它的主要用途是求解全源最小割/最大流。 前置知识： 一种快速的最大流算法（Dinic/ISAP均可，FF/EK不行，HLPP虽然快但不方便求最小割树），本文中采用Dinic。 最小割最大流定理：最小割=最大流 分治思想 下文中若无例外，均用\(O(\text{maxflow}(n,m))\)表示求一个\(n\)个点\(m\)条边的图上任意两点之间的最大流/最小割的时间复杂度。 建立 首先我们将全图看成一个集合。然后我们任选两个点\(s,t\)跑一遍最大流。 然后你会发现，我们可以通过源点是...

简要题意 四边形不等式是一种dp优化策略。多用于2DDP。 内容 对于区间\([l,r]\)带来的贡献\(w(l,r)\)，如果其满足： 对于\(L\leql\leqr\leqR\)，\(w(L,r)+w(l,R)\leqw(L,R)+w(l,r)\) 则称\(w\)满足四边形不等式。特别地，如果上式符号取等，则称其满足四边形恒等式。 注：上面的不等式可以记成：交叉小于包含。 四边形不等式优化基础：对于一个dp\(f(i,j)\)，如果其最优决策点（即第三维枚举的最优位置）\(s(i,j)\)满足\({s(i,j-1)\leqs(i,j)\leqs(i+1,j)}\)，则可以用此方法将时间...

约定 \(A\perpB\)表示\(\gcd(A,B)=1\)。 \(A\midB\)表示\(B\equiv0\pmod{A}(A\neq0)\)。 引入 考虑以下这道题： 有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？——《孫子算經》 也就是说，求出下列关于\(x\)方程组的最小整数解： \[\begin{cases}x\equiv2\pmod{3}\\x\equiv3\pmod{5}\\x\equiv2\pmod{7}\end{cases}\] 解析 首先我们考虑什么时候\(\equiv3\pmod{3}\)，什么时候\(\equiv3\pmod{5}\...

简介 大步小步(BabyStepGiantStep)算法，可以在\(O(\sqrt{p}\cdotf(p))\)的时间复杂度内（\(f(p)\)为一个大小为\(p\)的映射结构（如map、hashtable）进行单次读取/随机访问的时间复杂度）内解下列关于\(x\)的方程（离散对数方程）： \[a^{x}\equivb\pmod{p}\] 其中\(\mathbf{p\in\mathbb{P},a\perpp}\)。 思路 由于欧拉定理\(a\perpp,a^{b}\equiva^{b\bmod\varphi(p)}\pmod{p}\)，可以得到： \[a^{x\bmod(p-1)}...