## 斜率优化 斜率优化的核心思想是将转移方程变为形如 $y = kx +b$ 的形式，这样我们就需要解决 $n$ 个线性规划问题。在第 $i$ 个线性规划问题当中，我们的点集是 $S$，同时有斜率 $k_i$，假设这个线性规划的最小答案（截距）为 $b_i$ 则会向点集中添加一个新点 $(x_i, f(b_i))$，$f$ 是一个因题而异的函数。…

点分治 解决的问题 常用于解决树上大规模的路径问题。 基本思想 由于树上所有的路径都可以转化为经过重心的路径和没有经过重心的路径，对于前者可以直接 $O(n)$ 处理，对于后者则可以递归子树处理。 时间复杂度是 $O(n \log n)$。 算法步骤 寻找树的重心，将其作为根。 求出所有端点是根的路径。 求解问题，并递归子树回到第一步。 细节 找重…

解决的问题 博客 洛谷专栏 矩阵乘法在图论中常用于(定长/限制类)路径统计和最短路问题。此类型题目的时间复杂度往往是 $O(n^3 \log k)$，故此类题目的点数不应过大。 OI-wiki 一些代码技巧 struct Mat { int n; vector<VI> A; vector<int>& operator…

1 线段树 1.1 什么是线段树？ 线段树在算法竞赛中常用于区间操作。时间复杂度$O(\log n)$。 1.2 线段树的应用 1.2.1 线段树的基本应用 顾名思义，区间修改，区间查询。 1.2.2 线段树最大字段和问题上的运用 问题描述： 操作一：进行单点修改。 操作二：给定 $l$ 和 $r$，问 $[l, r]$ 中的最大的子段和是多少？ …