泪痕@一语成谶
辗转当作浮生妖,流离惊似尘世鬼
析合树 析合树
摘要 作为一个没有去过 WC2019 的人去啃 WC 的课件。别问我为什么这么菜。 翻的时侯翻到一个友好的标题:《简单的连续段数据结构》。打开后,咦!析合树! 另外解释一下本文可能用到的符号: 逻辑与, 逻辑或
2019.06.27
线段树与历史区间最值问题 线段树与历史区间最值问题
摘要 读 jry《区间最值操作与历史最值问题》 前言仍然是线段树的应用问题。在前文中我们探讨了线段树的基及其应用。如果对这方面了解较少的同学请移步《线段树初步》、《线段树应用》。本文将继续讲解线段树在区间最值与历史最值问题上的应用。 区间
2019.06.19
从树套树浅析常用结构的特性 从树套树浅析常用结构的特性
摘要 2019.6.18 编入精选文章 作者严正声名:本文比较沙雕。 另外,本文并不是 “树套树入门” 的文章,而是一篇议论性文章。议论性文章是指可能内容较受争议。 在我写这文章的时侯,输入法:蜀涛数,树桃树,树套数…… emm 就是没有树
2019.06.17
[国家集训队]Middle [国家集训队]Middle
摘要 题意:对于一个数列每次询问 ,求左端点在 右端点在 的区间的中位数的最大值。偶数的情况下标向下取整。 . 对于求这种答案在某一维度上单调的最值问题,
2019.05.21
线段树应用 线段树应用
摘要 啃一下线段树的课件。不过 SYF 是真的强,放一个课件中的 Scene: 提起线段树,大家肯定想起了那端令人窒息的经历: 看题:WOC,树套树套树套树? 写题:TMD,这得写上一年啊! 看榜:报警了,为什么高中生这么快就写完了?
2019.05.21
NOI2005 维护数列 NOI2005 维护数列
摘要 题意:维护一个数列支持 6 种操作:在某一位置插入 / 删除 / 覆盖 / 翻转 / 求和一段数字;求整个数列的最大的连续一段的数字的和。 既然这个序列的形态变化,自然想到平衡树维护。然后,我就调了 6 小时 emmm 打覆盖和翻转
2019.05.21
[SP11460]TTM - To the moon [SP11460]TTM - To the moon
摘要 题意:可持久化区间修改查询。 . 标记永久化在主席树上做区间查询,标记持久化。主席树直接维护序列区间和。做修改的时侯,我们对 log 个区间的结点打标记,但是不下传。查询的时侯,遇到路径上标记就累加对应标记
2019.05.20
FHQ Treap 入门 FHQ Treap 入门
摘要 整整四个月的沉寂,四个月的恐惧自闭,就在最后的 6 个小时,在凌晨 12 点 48 分,他醒了!扼住了平衡树的咽喉 emmm(手动滑稽) FHQ Treap | Treap | Splay大概讲一下神奇的 FHQ Treap 吧,它
2019.05.18
可持久化数据结构(三) 可持久化数据结构(三)
摘要 本文介绍了可持久化块状链表和可持久化平衡树。 块状链表的持久化首先讲一下这玩意儿,它就是 个用链表连起的数组。 相邻两个块大小之和大于等于 ,单个块大小小于等于 $O(2\sqrt
2019.05.17
浅谈一类分治算法 浅谈一类分治算法
摘要 仍然是啃论文,这次啃一啃数据结构的部分 修改与询问我们常常遇到数据结构题,要求我们维护修改与询问的操作。这些题目的要求各不相同,而操作之间的关系也各不相同。在满足特定关系的操作中,我们利用条件的线性性与相关性,可以将一类动态问题转化
2019.05.05
[Luogu3801] 红色的幻想乡 [Luogu3801] 红色的幻想乡
摘要 今天不是打题的好日子,以至于我和 90 分杠上了 一个 的方格地区,一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上,向东南西北四个方向各发出一条无限长的红雾,可以影响到整行 / 整列,但不
2019.04.30
[SCOI2015] 情报传递 [SCOI2015] 情报传递
摘要 有趣的树剖 + 主席树题 奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严
2019.04.09
[POI2014]KUR-Couriers [POI2014]KUR-Couriers
摘要 给一个数列,每次询问一个区间内有没有一个数出现次数严格超过一半. . 复习一下主席树~ 区间 对应版本 的权值线段树的差。每次查询当前结点的左右儿子结点的大小
2019.04.05
[POI2007]TET-Tetris Attack [POI2007]TET-Tetris Attack
摘要 题意:给定一个长度为 的序列, 各出现两次,可以交换相邻两项,两个同样的数相邻会消失,求把所有数对消的最小交换次数,输出方案。 . 一看就是一个树状数组的问题,关键是
2019.04.05
[CQOI2011] 动态逆序对 [CQOI2011] 动态逆序对
题意给出一个 的排列 ,要求做 次删除操作,每次删掉一个数 ,求每次删除操作前整个序列的逆序对。 . 教训这道题告诉我永远不要相信 $
2019.01.24
[SDOI2010] 粟粟的书架 [SDOI2010] 粟粟的书架
题意给出一个矩阵 ,要求回答 个以下询问: x1,y1,x2,y2,h 在以 为左上角,以 为右下角的子矩阵中找出 数使得这些数的和大于等于 . 要求最小化
2019.01.24
可持久化数据结构(二) 可持久化数据结构(二)
引言本文上接《可持久化数据结构(一)》,简单介绍了动态主席树。然后主要讲解了各类求第 K 小值的算法。 权值线段树的运算仍然是主席树的部分,我们先系统讲解权值线段树的运算 考虑两颗结构相同的权值线段树 ,那么定义有如下运算:
2019.01.23
可持久化数据结构(一) 可持久化数据结构(一)
前言有没有发现,很多数据结构的前面加上一个 “可持久化”,难度就上了一两个档次? 本文就从基础的可持久化数组入门,同时解释可持久化的含义 例题引入LuoguP3919【模板】可持久化数组 如题,你需要维护这样的一个长度为 N 的数组,支
2019.01.19
Splay 进阶 Splay 进阶
前言splay 初步 里面提到了 splay 的拓展性 其实 splay 不只是用于维护二叉搜索树,有时候也会脱离二叉搜索树的范畴 Splay 维护区间信息区间信息通常可以用线段树或者树状数组维护,不过不可忽略的是 Splay 也可以维护
2019.01.18
[ZJOI2006] 书架 [ZJOI2006] 书架
题意要求对一个元素互不相同的整数序列维护以下操作: 把某个数放到序列开头(左端) 把某个数放到序列结尾 把某个数和它左边的数交换 把某个数和它右边的数交换 询问某一个数字在序列的位置 询问在序列上某一位置的数是多少 $n,m\leq 8
2019.01.18
1 / 2