文章

https://www.luogu.org/problemnew/show/P5055 写了好久啊 看到网上的模板都好奇怪，参数好多好多的，就没看模板瞎写 有几个坑点： Copy 节点的时候注意判断你要 Copy 的是不是空节点，Copy 了空节点就 GG 了 Push Down 的时候两个儿子节点 阅读更多…

第一个操作显然是不要考虑的…… 考虑第二个操作怎么办 (实际上是超级 easy 的) 每个节点维护一个值 sum，表示 $Splay$ 中它子树的和，每个点的权值为 1(黑)0(白)。 对于这个操作，我们可以先 $split(1,x)$ ，现在 x 是这个 $Splay$ 的 阅读更多…

兑现诺言不咕咕 直接丢演示文稿： https://www.mina.moe/wp-content/uploads/2019/01/LeafyTree.pdf PDF 中讲解了 Leafy Tree 实现二叉搜索树 Leafy Tree 实现加权平衡树 Leafy Tree 提取区间 可持久化 Lea 阅读更多…

click here! 比赛的时候看这题过的人多也去看了看，结果发现自己压根不会处理操作 3，然后就弃了（太菜了 QAQ 首先因为 $v\leq 7000$并且询问的是一个数的奇偶性，我们容易想到将每个集合用一个大小为 $7000$的 $bitset$来维护每个数的奇偶性。 操作 $1,2,4$用这 阅读更多…

click here! 题目大意就是给一个 n，每次操作能将 n 等概率变成它的一个因数，求 k 次操作后的期望 比赛的时候想到质因数分解了，然而还是因为概率 dp 太弱没打出来 我们先考虑数 $p^{cnt}$的答案 设 $f_{i,j}$表示第 $i$次操作后 $p^j$为当前数的概率 我们容易 阅读更多…

https://www.luogu.org/problemnew/show/P3835 题目大意和普通平衡树一题差不多，只不过需要提供历史版本的支持（会指定当前版本由哪个历史版本复制而来）这题可以用可持久化 Treap 做但我还没试过（另外 Splay 不能可持久化的原因是它的复杂度是均摊的，替 阅读更多…

Upd：本文章因代码写太丑被大佬 D 了请谨慎查看 题面就不多说了 https://www.mina.moe/BZPRO/JudgeOnline/3223.html 这个怎么说呢，得用 Leafy Tree 提取区间 可是 ctsc2018 的论文集并没有讲 Leafy Tree 怎么区间操作 提取 阅读更多…

每个楼房，还有单点修改操作。简单的想到用线段树来维护信息。 显然线段树只需要维护 y/x 即可，对于每一个楼房，能看见的条件就是前面楼房的 y/x 的严格小于当前楼房的 y/x。 线段树的区间修改不再赘述。 那么怎么维护可以看到的楼房数呢？ 考虑在线段树的每一个节点上用一个变量 sum 来表示从这个 阅读更多…

Remmina 酱白天要做文化课，只能晚上来写题了，现在凌晨啦 刚开始学平衡树好吃力啊 蟹蟹 XZY 学长之前的指导，总算是照着论文把 Leafy Tree 写出来啦 到时候可能会发文章（或者 PPT）来讲讲这个算法，确实还算比较好写的吧 当做模板放在这里啦，具体操作论文讲的很清楚，就是 CTSC 阅读更多…