【模板】权值线段树套序列线段树 P3380 【模板】二逼平衡树（树套树） 主要思路如下： 外层为权值线段树，内层为动态开点线段树，也就是每个权值线段树上的节点开一个动态开点线段树。 外层的权值线段树支持查询排名，内层的线段树限制了区间。实际上就是在普通权值线段树上查询的价值变成了在其线段树上区间查询返回的值。 对于这道模板题，我们先写几个函数： 插入 下方的update为外层...

点分治 点分治是一种树形分治的算法，它选择当前连通块一个重心，将树分成多个连通块进行处理，然后对每个连通块进行分治递归。 树的重心 树上的一个点，满足它的儿子的 \(size\) 的最大值最小。 可以证明，一个树有一个或者两个重心。若有两个重心，它俩一定是直接相连的。 处理问题 求树上给定路径联通的点的对数。我们发现将树分治后，形成了若干个连通块，而且这些连通块必定经过重心。...

P3384 【模板】重链剖分/树链剖分 适用问题 对一个给定的树，维护（修改、查询）其节点点权/边权，操作可 \(O(\log n)\) 次处理（如路径、子树）。 实现 将一棵树剖分成若干条链，每一条链通过区间数据结构维护。 将一个点的子树中最大的那个做为重儿子，其他的叫做轻儿子，对于所有点的重儿子连的链称为重链。我们将重链作为主链，将轻儿子构成的其他轻链加在重链的后面。很明显，...

逆元 求一个数的逆元，就是说这个数乘以它的逆元恰好等于1。在 \(\mathbb{Z}_p\) 内，设 \(a\),\(b\) 互质，则 \(a\) 的逆元记作 \(a^-1\)，定义为 \(b\)，使得 \(ab=1\)。 \(p\) 是素数时，逆元唯一存在。 \(p\) 是合数时，逆元可能不存在。 求逆元 扩展欧几里得 适用于 \(p\) 不为素数的情况。 解方程组 \(...

笛卡尔树 笛卡尔树（Cartesian tree）是一种树形数据结构，每个节点都是一个区间，树的根节点表示整个区间，左儿子表示区间的左半部分，右儿子表示区间的右半部分。 笛卡尔树可以通过单调栈 \(O(n)\) 静态建造。 例题 P2659美丽的序列 题意 找出一个序列的所有子段中子段长度乘段内元素最小值的最大值。 思路 我们需要找出所有子段中贡献最大的，并且一个...

算法介绍 模拟退火是一种最优化随机化算法。什么叫随机化算法？就是抽奖抽正解 一般用于求解最优解，即最优化问题，而且一般比较适合于小数据的最优解和大数据的近似最优解。 算法步骤 每次迭代都随机选择一个解，然后模拟退火得到该解的邻域最优解，如果邻域最优解比当前解更优，则接受该邻域最优解小，则更新当前解为该解。 模拟退火步骤如下： 先初始化温度，当前解和当前答案 如果温度小于最终...

类欧几里得算法之所以得名是因为其算法复杂度证明与扩展欧几里得算法类似。 我认为类欧更偏向于是一种思想。 其主要思想就是寻找可以简便计算的边界，然后通过化式子将不同情况化为边界递归计算。 通过几个具体的例子，可以更好地理解其思想。 P5170 【模板】类欧几里得算法 推导 \[ f(a,b,c,n)=\sum_{i=0}^n \lfloor\frac{ai+b}{c}\rf...

定义 基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。 同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素...

线性筛 欧拉筛 线性筛（又称欧拉筛）是一种线性求素数的筛法，可以在 \(O(n)\) 的时间内找出 \(n\) 以内的所有素数。 线性筛的基本思想是，对于 \(i\) 从 \(2\) 到 \(n\) 的每个数，如果它不是素数，则枚举已筛出的每个素数，若其非 \(i\) 的因子，则将 \(i\) 乘上该素数的积标记为已被筛掉。直到枚举到 \(i\) 的最小质因子。这样，当 \(i\)...

懒标记 线段树要做到其 \(O(\log n)\) 的更新和查询，就需要用到懒标记。 懒标记的作用是，当我们对线段树的某些节点（区间）进行更新时，我们并不立即更新这些节点的值，而是将这些更新操作延迟到下一次查询或更新时再进行。 洛谷已经为我们排好了对线段树的逐层深度学习XD P3372 【模板】线段树 1 1234567891011121314151617181920212...