珂朵莉树 参考资料: 珂朵莉树/颜色段均摊 - OI Wiki 珂朵莉树（Chtholly Tree），又称ODT。源自 CF896C。 这个名称指代的是一种使用 平衡树 或 链表 维护「颜色段均摊」的技巧，而不是一种特定的数据结构。其核心思想是将指相同的一段区间合并成一个结点处理。相较于传统的线段树等数据结构，对于含有区间覆盖的操作问题，珂朵莉树可以更加方便地维护每个被覆盖区间的值。 实现（std::set） 结点类型 123456struct Node_t{ int l,r; mutable int v; //mutable能突破 const 的限制，使变量永远可变 Node_t(const int &il,const int &ir,const int &iv):l(il),r(ir),v(iv){} //构造函数 bool operator<(const Node_t &o) const {return l<o.l;}}; ...

图论-DFS/BFS 参考资料: DFS（图论） - OI Wiki 深度优先搜索DFS 引入 ​ 深度优先搜索 (Depth First Search)，简称 深搜 或者 DFS，是一种用于遍历或搜索树或图的算法。顾名思义，深搜就是每次向着下一层次的搜索。 ​ 与之相对的是 BFS , 但两者除了遍历图的连通块以外，用途完全不同。 过程 ​ DFS 最关键的地方就是通过栈实现 “回退” 至上一结点以遍历同一层次的结点，我们也可以通过递归实现(这是主流用法)，毕竟递归是依靠栈实现的。访问每个结点时得为其打上标记，避免重复访问。 ​ 显然我们可以得到这样一个DFS结构 1234567dfs(v){//v为图中的一个顶点，有时也可以是其他抽象的概念，如dp状态 //标记v for u in v相邻的结点{ if 如果u没有标记 dfs(u) //递归访问u结点 }} 性质 ​ 该算法通常的时间复杂度为 \(O(n+m)\) ，空间复杂度为 \(O(n)\), 其中 \( ...

《硅谷之火》部分简述 b { all: unset; font-weight:bold; } 内容太多，目前只做了第一章的简述，对此感兴趣可以看看原书《硅谷之火》 ​ 尽管个人计算机问世于20世纪70年代中期、巨型计算机要回溯到20世纪50年代，我们甚至能够追溯到19世纪末对未来的幻想。 火种 上帝保佑，我真希望计算能用蒸汽运行。 ——查尔斯·巴贝奇 ​ 这是火种。 ​ 诗人拜伦和雪莱注意到科学带来的变化，交流着人工生命与人工思维，雪莱夫人玛丽·雪莱由此创作了《弗兰肯斯坦》，科学怪人这一小说形象令人望而生畏。1833年，查尔斯·巴贝奇谈起利用蒸汽进行计算并真的开始实施，他认为这“分析机”将会让人们从枯燥的脑力劳动中解放出来，而拜伦女儿艾达·拜伦极力支持并提供帮助，由于她做的工作，人们视艾达为世界上第一位程序员(Ada语言的命名因此而生)。巴贝奇关于分析机的3种设计均已失败告终，他设计的差分机虽简单而显雄心，却也仍未实现。1991年，伦敦科学博物馆的一位馆长多伦·斯沃德成功用巴贝奇时代的技术、材料造出了巴贝奇的差分机。事实上，巴贝奇设 ...

.red{ color:red; font-weight:600; //bold为700，normal为400 } .lbold{ font-weight:bold; font-size:24px; //默认16px } .bold{ font-weight: bold; } details { border: 1px solid #ccc; background-color: #f0f8ff; /* 浅蓝，适合白天 */ border-radius: 6px; padding: 0.5em; transition: background-color 0.3s ease, border-color 0.3s ease; } ...

参考资料：动态规划基础 - OI Wiki 目前绝大多数内容摘自OI-Wiki,个人理解重构等后续更新 动态规划初步 ​ 动态规划(Dynamic Programming)，简称DP，它本身不是一种特定的算法，而是一种思想。当状态变动与之前或之后状态有关时，我们往往可以使用方程来描述这种关系。这种方程被称作状态转移方程。 动态规划原理 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。 最优子结构 具有最优子结构也可能是用适合贪心的方法求解。 注意要确保我们考察了最优解中用到的所有子问题 证明问题最优解的第一个组成部分是做出一个选择; 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解，你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间； 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本省的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题中的解用 ...

线段树 参考: 线段树 - OI Wiki ​ 线段树是一种二叉搜索树、平衡二叉树，对于区间的修改、维护和查询时间复杂度优化为log级别。对区间不断做平分区间，直到划分到只有一个或多个数据的区间，可表示区间的和或者最小最大值。在进行更新区间操作时，通过小区间更新大区间。 ​ 对于下面的内容，我们主要针对于区间加法的线段树(即其节点表示区间之和)。 ​ 局限性： 问题需满足区间加法：对于[L,R]的区间，它的答案可以由[L,M]和[M+1,R]的答案合并求出。 不满足区间的众数、区间最长连续问题、最长不下降问题等。 建树 当我们拥有数组 \(a\) 并且用来区间求和之类的问题时，我们可以这样做： ​ 以堆的方式实现存储(树形数组)，将元素放至树的最下面一层。 由于我们使用树形数组，为了存储下数组 \(a\), 数组 \(tree\) 的长度应当为 \(a\) 的四倍，并且初始节点位置为1。同时，当前区间[s,t]只有一个元素时(即s==t)，意味着当前节点为叶子节点，就要让当前节点 \(tree[p] = a[s]\)。对于其它的情况，我们 ...

快速幂 快速幂，即快速取幂的技巧。 对于在取幂过程中，需要不断取模的过程中（例如费马小定理求模逆元）时，单纯的pow函数已经不再满足我们的需要。我们需要明白pow函数的原理，以方便我们“魔改”pow函数。 定义 快速幂，二进制取幂（Binary Exponentiation),是一个在 \(O(logn)\) 的时间计算 \(a^n\) 的小技巧。 实现 递归形式 按幂的定义而言，\(a^n\) 等于 \(n\) 个 \(a\) 相乘，如果我们按照这样的定义实现算法的话，当 \(n\) 足够大时，资源的开销就很大了。 根据指数乘法，\(a^{b+c}=a^{b}+a^{c}\), 当 \(n\) 为偶数时, \(a^{n}=a^{\frac{n}{2}}·a^{\frac{n}{2}}\), 对于 \(n\) 为奇数的情况, 无非是在此基础上再乘以 \(a\) 罢了。因此，我们很容易就能得到实现快速幂的递归形式。 1234567long long pow(long long a, long long b){ if(b == 0) ret ...

并查集 参考资料:并查集 - OI Wiki 基本概念 并查集是一种管理元素所属的数据结构,实现为一个森林，每颗树表示一个集合,树中的节点表示对应集合的元素。 显然，并查集支持两种操作: 合并(union): 合并两个元素各自所属的集合 查询(find): 查询某个元素所属的集合 初始化 初始时，每个元素都位于一个单独的集合表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。 1234struct dsu{ vector<size_t> pa; explicit dsu(size_t size):pa(size){iota(pa.begin(),pa.end(),0);}} 查询 我们需要沿着树向上移动，直至找到根节点。由于根节点的父亲是自己本身，因此递归的终止应该是pa[x] == x。 123size_t dsu::find(size_t x){ return pa[x] == x? x: find(pa[x]);} 路径压缩 查询 ...