“笑って走っていく日も 泣きながら帰る日も この街と共に生きてる”——《街》 分析 操作过后的数一定至少变为原来的 12\frac{1}{2}21,所以问题变成了如何判断区间内是否会有数被修改。 可以维护 lcm\text{lcm...
P5494 题解 & 平衡树合并
这是一篇平衡树合并题解,平衡树合并的复杂度 并不是假的,本题复杂度 O(nlogn)O(n \log n)O(nlogn),更通用的可以证明到 O(log2n)O(\log^2 n)O(log2n),比如支持序列 全局加全局取膜。...
切比雪夫距离与曼哈顿距离
内含高维曼哈顿-切比雪夫转换。 定义 曼哈顿距离:∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|∣x1−x2∣+∣y1−y2∣ 切比雪夫距离:max(∣x1−x2∣,∣y1−y2∣)\max(|x_1...
P2120 题解
“生きてく意味があると感じるよ…確かに!”——《Nameless Love Song》 分析 首先写个 n2n^2n2 dp 转移 fi=minj=1i−1(fj+∑k=j+1i(xi−xk)pk)+ci=minj=1i−1(f...
聊聊 dsu on tree
契约签订完毕,接下来要认真起来了。 简介 对于子树查询类问题,大多可以 dfs 序然后上数据结构,不行就树上莫队。 一个方法是 dsu on tree,是一个好写的复杂度 O(nlogn)O(n \log n)O(nlogn) 离...
真·浅谈高维前缀和/sosdp
夜空是否全然知晓? 高维前缀和/sosdp 计算高维前缀和可以不用容斥,而是对每一维分别做前缀和,复杂度为 O(kn)O(kn)O(kn),其中 kkk 是维度。 对于子集求和问题,相当于二进制下的 111 可以选 000 或 11...
真·浅谈线性基
或许是该努努力了呢,快要来不及了。 异或线性基 简单来说,线性基是一个数的集合,每个序列都拥有一个线性基,线性基中的若干个数异或起来原序列中的任意一个数。 重要性质: 原序列中的任意一个数都能通过线性基中的若干个数异或得到。 线性...
整体二分浅谈
浅浅的总结一下简单情况。 适用范围 可以使用整体二分解决的题目需要满足以下性质: 询问的答案具有可二分性 修改对判定答案的贡献互相独立,修改之间互不影响效果 修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值 贡献满足交...
P4732 题解
“这样的我会被谁拯救吗 你发现了吧” —— 《月光掌》 分析 设第 iii 次撤销操作要撤销的是 jjj,那么 iii 到 jjj 的操作中不存在优先级比 jjj 小的,所以 jjj 到 iii 的操作不会在没撤销 iii 的情况下...
网络流常见建模
你眼中倒映的世界 一瞬永远 —— 《梦语》 分析 首先答案有单调性,考虑二分。 然后每次留下来的构成一颗三叉树,父亲是儿子的中位数,考虑树形 dp。 上很经典的中位数套路,设二分的值为 vvv,≥v\geq v≥v 的 gvg_vg...