标签:树

OI

[NOI2015]软件包管理器[树链剖分,线段树]

cgazn阅读(84)评论(0)赞(0)

题面 毒瘤数据结构复习系列. 设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1 卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0 线段树的区间覆盖只要把懒标记的+=改为=就行...

OI

[CF896C]Willem, Chtholly and Seniorious[ODT]

cgazn阅读(114)评论(0)赞(0)

为了更好的骗分完成CF558E A Simple Task和CF896C Willem, Chtholly and Seniorious, 特意学了这种新的毒瘤数据结构. ODT的思想很好理解, 就是把一段值相同的区间压缩为1个节点, 即每...

OI

[洛谷P4513]小白逛公园[线段树]

cgazn阅读(87)评论(0)赞(0)

题面 双倍经验: https://www.luogu.org/problem/SP1716 复习一下线段树, 老是写挂… 这道题是一种常见线段树处理连续子段问题的做法. 每个节点维护区间最大子段和, 从左端点开始的最大子段和, ...

OI

[POJ3630][HDU1671]Phone List[Trie]

cgazn阅读(59)评论(0)赞(0)

题面 这是一道Trie树模板题. Trie树也叫字典树, 采用类似字典一样的索引方法, 把边看做字符, 把多条字符串建立成树, 达到字符串快速检索, 资瓷插入和查找两个操作. Trie树的思想一句话概括就是相同的前缀共用同一条链, 在不同的...

OI

[POJ3784]Running Median[堆]

cgazn阅读(99)评论(0)赞(1)

题面 题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数). 设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分. 资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分...

OI

[洛谷P3384]【模板】树链剖分

cgazn阅读(57)评论(0)赞(0)

复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长… 考虑如何把一棵树通过编号处理成...