记录一下我们机房一位大佬的做法。 我们先把重叠的圆删去，考虑求出合并后的轮廓，即每个圆没有交的圆弧。 为了后面方便，我们要求每段圆弧是单调的。 枚举每个圆，求出他和其他圆的交点（用与 x 轴正半轴的夹角表示）。 那么两个节点间的圆弧是没用的，排序后，利用类似差分的思路即可。 图中红圈表示当前圆，绿点表示 +1，蓝点表示 -1，黄点表示 0。 用黄点是把圆分成 4 份单调的弧，起点为 0 ...

斜率优化与例题。

P2617 单点修改，区间查询第 kkk 小。 树套树 区间第 kkk 小的一种解法是用主席树，利用两个子树做差实现。 但加上单点修改后，直接做每次修改是 O(nlog⁡n)O(n\log n)O(nlogn) 的，复杂度太大。 考虑平衡询问和修改的复杂度。 我们在主席树外套一棵树状数组。 询问时把两个子树作差变成 log⁡n\log nlogn 个子树作差。 修改时只需要修改 log⁡n...

用 FFT 实现多项式乘法

Gym-102465k Dishonest Driver 给出一个字符串，两个相邻且相同子串可以进行压缩，问压缩后字符串最少有多少字符，n≤700n \le 700n≤700。 将两个相邻区间合并，且 nnn 很小，就很像是区间 DP。 定义 dpi,jdp_{i, j}dpi,j​ 表示 [i,j][i, j][i,j] 的压缩后最少字符数。 显然有两种合并，直接拼起来相加，或者将右区...

$\mu$ 的定义，性质，和几道例题。

邮局 加强版 加强加强版 普通版 dpi,k=min⁡j=0i−1dpj,k−1+w(j+1,i)dp_{i, k} = \min_{j=0}^{i-1}dp_{j, k - 1} + w(j + 1, i)dpi,k​=minj=0i−1​dpj,k−1​+w(j+1,i) 其中 dpi,kdp_{i, k}dpi,k​ 表示前 iii 个放 kkk 个邮局的最小代价，w(l,r)w(l...

一定要会 trie，不一定要会 kmp。 作者是个 fw，有些话不是很标准，还请见谅。 为了方便，接下来的 acam，没有特殊表明，均表示 AC自动机。 我们直接引入一道题目 P5357。 这题就是标准的模板，从中，我们可以得到 AC 的作用：统计文本串内各个模式串的个数。 我们回忆一下 trie 的作用：判断一个字符串在不在一堆字符串里。 这和题目很像，我们想想怎么建这棵 trie。 我们...

我们有这样一个问题：修改点权，询问链上的点权和。这明显是个树链剖分模版。
但如果还有这些操作呢：断开一条边，连上一条边，保证一直是森林。这就是动态树的一种问题。
而 LCT 就是解决这些问题的优秀数据结构。

普通最大流的实现与一些例题。