这篇文章受密码保护，输入密码才能阅读
题面 毒瘤数据结构复习系列. 设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1 卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0 线段树的区间覆盖只要把懒标记的+=改为=就行了 看到题解中还有一种更妙的做法: 只进行update操作, 统计线段树根节点sum值变化即可, 理论上常数是…
为了更好的骗分完成CF558E A Simple Task和CF896C Willem, Chtholly and Seniorious, 特意学了这种新的毒瘤数据结构. ODT的思想很好理解, 就是把一段值相同的区间压缩为1个节点, 即每个节点记录一个三元组$ (l,r,v)$, 表示区间$ [l,r]=v$. 然后把这些节点以l为关键字都丢到s…
题面 双倍经验: https://www.luogu.org/problem/SP1716 复习一下线段树, 老是写挂... 这道题是一种常见线段树处理连续子段问题的做法. 每个节点维护区间最大子段和, 从左端点开始的最大子段和, 从右端点开始的最大子段和, 区间和. 这样合并两个节点时就可以考虑以下几种情况: 对于合并后的从左端点开始的最大子段和…
这篇文章受密码保护，输入密码才能阅读
这篇文章受密码保护，输入密码才能阅读
这篇文章受密码保护，输入密码才能阅读
题面 这是一道Trie树模板题. Trie树也叫字典树, 采用类似字典一样的索引方法, 把边看做字符, 把多条字符串建立成树, 达到字符串快速检索, 资瓷插入和查找两个操作. Trie树的思想一句话概括就是相同的前缀共用同一条链, 在不同的地方产生分支, 在字符串的结束位置打标记. 每个节点有size个指针指向后继, size为字符集大小, 空间复…
题面 题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数). 设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分. 资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分别开一个大根堆left 小根堆right, 那么right.top()即为中位数. 每次加入一个数x, 若比当…
复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长... 考虑如何把一棵树通过编号处理成尽量少的链, 同时保证每棵子树/每条链的编号都连续. 容易发现dfs序就满足前者, 这样就保证了每棵子树都在一个连续区…