P15482 考虑先钦定哪种颜色的点不选，然后自下而上枚举，维护每个颜色可能为答案的水平线段，每遇到一个点就将其颜色的水平线段一分为二，然后统计答案即可。 维护水平线段可以用 set，统计答案可以离散化后树状数组。 每多一个点最多增加一条水平线段，所以总线段数是 O(n)O(n)O(n) 的。 123456789101112131415161718192021222324252627282...

P15534 由于每次询问是不同的货物，考虑离线。 从 u→vu \rightarrow vu→v 和 v→uv \rightarrow uv→u 的答案不同，我们将询问分成两段 u→LCAu \rightarrow \text{LCA}u→LCA，LCA→v\text{LCA} \rightarrow vLCA→v。 对于 u→LCAu \rightarrow \text{LCA}u→L...

对比一下写过的平衡树。

记录一下我们机房一位大佬的做法。 我们先把重叠的圆删去，考虑求出合并后的轮廓，即每个圆没有交的圆弧。 为了后面方便，我们要求每段圆弧是单调的。 枚举每个圆，求出他和其他圆的交点（用与 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...