dna049

再见了 dna049，我想重新开始（本站将于 2022-01-01 永久关闭）

主线任务：上 2100，支线任务：成为一名优秀的代码攻击者。 最近感觉自己又行了。就很想重新开始打 Codeforces，这里罗列一下从 2020/05/16 开始提交的(不是特别水的）AC 代码。想有生之年上一次黄，先定个小目标上个 ...

整体二分是 由 许昊然 于 2013 年集训队论文《浅谈数据结构题的几个非经典解法》提出的一类离线算法。 学习资料：oi-wiki，知乎 不修改版本看了 OI-wiki 老半天，终于懂了，其它就是求一个区间 $[L, R]$ 中小于某个数的 ...

可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。(OI-wiki 原话)，然而实际上我们常见的可持久化数据结构都是依赖于可持续化线段树。 ...

二维直方图最大矩形是一个特别经典的问题，利用单调栈即可在 $O(n)$ 复杂度解决，那么三维的呢？你会发现无从下手（暴力方法就不说了，没啥意思，最多就是多线程处理）。此题跨度之长，因此需要补的东西之多，值得单独写一篇博文。 时间线 2021 ...

首先莫队算法是一个离散算法，复杂度 $O(n \sqrt{m})$ 一般用于 $m$ 次长为 $n$ 的区间问题。 普通莫队首先按照左端点所在的块为第一关键字，再按照右端点升序为第二关键字排序。优化：如果都是从小到大，那么由于这样两个指标都 ...

本篇内容为 oi-wiki 字符串篇 的学习笔记，代码更新汇总。 字典树（Trie）假设在一堆仅有大/小写字母的字符串中，需要快速检测某个字符串是否存在，那么 Trie 是个不错的选择。 仅包含小写字母的 Trie（大写字母同理）12345 ...

图论还是一个特别强的工具。 为什么没有图论的 STL？代码更新汇总。 其他人的图论模板可做参考（其实我自己的够用了目前看） Nisiyama_Suzune 的图论模板 DQ9911 的模板 HDU 模板 也可以作为参考 存边方式 不涉及删 ...

在 Codeforces 有人问了我两个优化问题，一个是非线性规划（具体说是凸优化问题）。一般来说非线性规划没有什么具体的算法，但是凸优化，可以转化成凸包，然后转换成线段（如果是二维的）上的最值问题就搞定了。另一个是线性规划（所有线性规划其 ...

math e8899ed765713659fea7e6a843ae8311114a819ea3354d7df10e7abd6f6bcfce0f817463f574765ab057432b9eb31a ...