这是一篇平衡树合并题解，平衡树合并的复杂度 并不是假的，本题复杂度 O(nlog⁡n)O(n \log n)O(nlogn)，更通用的可以证明到 O(log⁡2n)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...

契约签订完毕，接下来要认真起来了。 简介 对于子树查询类问题，大多可以 dfs 序然后上数据结构，不行就树上莫队。 一个方法是 dsu on tree，是一个好写的复杂度 O(nlog⁡n)O(n \log n)O(nlogn) 离...

夜空是否全然知晓？ 高维前缀和/sosdp 计算高维前缀和可以不用容斥，而是对每一维分别做前缀和，复杂度为 O(kn)O(kn)O(kn)，其中 kkk 是维度。 对于子集求和问题，相当于二进制下的 111 可以选 000 或 11...

或许是该努努力了呢，快要来不及了。 异或线性基 简单来说，线性基是一个数的集合，每个序列都拥有一个线性基，线性基中的若干个数异或起来原序列中的任意一个数。 重要性质： 原序列中的任意一个数都能通过线性基中的若干个数异或得到。 线性...

浅浅的总结一下简单情况。 适用范围 可以使用整体二分解决的题目需要满足以下性质： 询问的答案具有可二分性 修改对判定答案的贡献互相独立，修改之间互不影响效果 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值 贡献满足交...

本文主要讲建图方法，定义和证明内容较少。 正好网络流二十四题做完了整理下。 目录 网络流模型 最大流最小割 最小割树 平面图最小割 费用流 SSP 算法 有负圈的费用流 上下界建模 无源汇上下界可行流 有源汇上下界...

模拟赛考到了，正好写一下。 简介 圆方树是一种将图变成树的方法，解决一些路径连通性相关的东西或者是仙人掌。 描述 前置知识：点双连通分量。以下不考虑孤立点。 在圆方树中，原来的点为圆点，点双为方点。每个点双内部是一个菊花图 [1]...

都是典中典，我之前还不是很会。 简介 对于一颗正常的线段树，如果要支持所有版本都既可以访问又可以修改（完全可持久化），对于每个版本保存一颗线段树是不可接受的。 发现每次修改操作修改的点的个数只有 log⁡n\log nlogn 个，...

发现这部分学的最烂，稍微整理下。 强连通分量 定义 强连通的定义：有向图 GGG 强连通，当且仅当 GGG 的任意两个节点联通。 强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连...