CF833B-线段树优化DP 题意 将一个长为\(n\)的序列分成\(k\)段，每段贡献为其中不同数字的个数，求最大贡献和。\(n\leq 35000,k\leq 50\)。 思路 此处感谢@gxy001 聚铑的精彩讲解 先考虑暴力DP，可以想到一个时空复杂度\(O(n^2k)\)的方法，即记录前i个数字分成了j段。我们现在来思考几个问题来优化这个操作： 对于一个数字，它对那...

P6845 [CEOI2019] Dynamic Diameter 题意 一颗带权树，每次更改一条边的权，每次修改后求出最大直径。强制在线。 思路 \(O(n\log^2n)\) 的暴力做法。 根据经典结论，对于两个点集的树上最大直径（权值非负），并集点集的树上最大直径的端点一定是原四个端点中的两个。 那么我们就可以用线段树维护点集，合并时 \(O(\log n)\) 查询两点...

我的第一篇洛谷博客就是扫描线。虽然那时候什么也不懂，也非常幼稚，甚至不知扫描线的原理是如何，只是一门心思地去做，就像面对未知的生活。 扫描线处理矩阵面积之和的问题，当然它们会有互相覆盖而不能直接加起来。 扫描线就是从下往上一次扫描“线”，然后用线将图分成多个区域，累加即可。用线段树记录横坐标此时扫描线处的长度。 用 Xi 表示第 \(i\) 条竖直的线（用来划分区间），用 l...

【模板】权值线段树套序列线段树 P3380 【模板】二逼平衡树（树套树） 主要思路如下： 外层为权值线段树，内层为动态开点线段树，也就是每个权值线段树上的节点开一个动态开点线段树。 外层的权值线段树支持查询排名，内层的线段树限制了区间。实际上就是在普通权值线段树上查询的价值变成了在其线段树上区间查询返回的值。 对于这道模板题，我们先写几个函数： 插入 下方的update为外层...

懒标记 线段树要做到其 \(O(\log n)\) 的更新和查询，就需要用到懒标记。 懒标记的作用是，当我们对线段树的某些节点（区间）进行更新时，我们并不立即更新这些节点的值，而是将这些更新操作延迟到下一次查询或更新时再进行。 洛谷已经为我们排好了对线段树的逐层深度学习XD P3372 【模板】线段树 1 1234567891011121314151617181920212...

线段树在维护区间时可以维护任何区间信息，比如，一个单调栈。 P4198 楼房重建 题意：维护全局最大上升序列大小。 更新 线段树当前节点存储整个区间的最大值，对于该题，左子树的区间答案可以直接继承，然后用左子树区间的最大值查询右子树的答案并记录在该节点上。 123456void update(const int &x,const double &k,const in...