[NOI2015]软件包管理器[树链剖分,线段树]
题面 毒瘤数据结构复习系列. 设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1 卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0 线段树的区间覆盖只要把懒标记的+=改为=就行...
题面 毒瘤数据结构复习系列. 设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1 卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0 线段树的区间覆盖只要把懒标记的+=改为=就行...
题面 双倍经验: https://www.luogu.org/problem/SP1716 复习一下线段树, 老是写挂… 这道题是一种常见线段树处理连续子段问题的做法. 每个节点维护区间最大子段和, 从左端点开始的最大子段和, ...
无法提供摘要。这是一篇受保护的文章。
无法提供摘要。这是一篇受保护的文章。
复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长… 考虑如何把一棵树通过编号处理成...