万字长文·树上启发式合并入门经典树上启发式合并是一种十分方便的将暴力算法优化至正解的优美的暴力 对于一类树上统计问题 如果我们使用 可以解决一类树上统计问题 的点分治来做 会不好写 这样就可以引出树上启发式合并了 先给出例题 CF600E 有一棵 n 个结点的以 1 号结点为根的有根树 ...

傅里叶变换（FFT）初步概述傅里叶变换（FFT）是各种多项式模板算法的基础 可以认为是重多省选内容中相对简单的一个 那么FFT是干什么的呢？ 利用卷积思想求多项式的乘积 时间复杂度O（nlogn） 初回忆初中刚学多项式乘法时 是不是感觉非常麻烦 例子$$(x^2+3x+6)(x^3+x^2+ ...

决策单调性优化胡扯四边形不等式设二元函数$w(i,j)$ 对于$a<=b<=c<=d$ 若$w(a,d)+w(b,c)>=w(a,c)+w(b,d)$ 则函数$w$满足四边形不等式 引理1若二元函数$w(i,j)$满足对于$i& ...

决策单调性分治优化对于一类方程： dp[ i ] [ j ] = min( k < j ){ dp[ i - 1 ] [ k ] +cost[ k ] [ j ] } 若cost满足四边形不等式 我们可以对它进行决策单调性优化 但不同与直接二分 因为方程是分阶段的（第一维） ...

可能是多项式模板全家桶(不到)万字长文或许是较好理解的板子讲解本文无代码 否则您将学习每天一个常数爆炸小技巧 qwq 阅读本文约需9分钟: 前置知识:复数虚数单位虚数单位$i=\sqrt{(-1)}$ 定义复数是形如$a+bi$的数 运算加法复数 $x=(a+bi),y ...

字符串入土[伪]-想要成为万字长文事实1字符串算法不是线性就是去线性的路上 字符串hash思想: 我们发现字符串可以看作一个k进制数 只是太长 我们可以对它取模 从而判断两串是否相等 讲完了 无代码qwq KMP思考匹配两串 发现第一次失配的位置: 暴力算法 我们直接再次暴力跳转 但如果 ...

拉格朗日插值法入门经典若我们有n对过某曲线的点 如何构造一n-1次多项式使其通过这些点 我们使用拉格朗日插值法 1.经典法对于每个点$k$ 我们单独构造一个多项式$f_k(x)$使得除$k$ 外所有点在该多项式中取0 易构造出$$f_k(x)=\prod_{i=1,i!& ...

最大流增广路算法从流量为0的容许流开始 不断寻找增流路径增加容许流流量 直到无法增加 Ford-Fulkerson 标号算法记录$v_e=c_e-f_e$为一条边的剩余容量定义残量网络 对于每条边$e=(u,v)$,其边权为$v_e$,并对其增加一条反向边$e^, ...

点分树是一种将点分治离线下来的算法 通过点分治将每一层的重心作为儿子链接到上一层的重心上 可以发现这样的一棵点分治重构树只有logn层 枚举点对的代价只有nlogn 而这棵树上任两点的lca必在两点原树路径上 所以可以使暴力算法在这上面达到nlogn 并且带修改题目往往只会修改点权而不会修改 ...

点分治点分治是解决一类树上计数问题的有效方法可以通过分治达到较优的复杂度 一个例子给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。考虑暴力怎么做 是不是枚举点对 求路径长度 显然 这样做在通过各种预处理后最优复杂度仍是n*n的我们可以分治 考虑在每颗子树中的点对的路径长度 显然 ...