左偏树 & 可并堆
左偏树\可并堆
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132507434
https://www.luogu.com.cn/problem/P3377
作用：可并堆
形态：堆+满二叉树
即左节点最小深度大于等于右节点最小深度
合并过程：
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2024-08-22
8.22 T4 （吉司机线段树）伤痕累累的心，在暴雨中仍然放声歌唱
8.22 T4 （吉司机线段树）伤痕累累的心，在暴雨中仍然放声歌唱 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141429914 http://cplusoj.com/d/senior/p/SS240709D 假设现在只有 [1,x][1,x][1,x] 考虑一个数的贡献区间为 r−l−1r-l-1r−l−1 ， l,rl,rl,r 为左右第一个比它大的数的坐标 此时的答案是 ∑r−∑l−x\sum r-\sum l-x∑r−∑l−x 。我们不妨先算 ∑...
2023-09-01
善用值域数据结构+操作离线：1864F
善用值域数据结构+操作离线：1864F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132631673 发现题目中有两个维度： 维护数值，发布计算某种情况下的答案 多个查询 两个维度，发现很难分开做。考虑对操作离线，同时维护两个维度的东西。 类似线段操作，左边入时±，右边出时-+ 本质是一种扫描线的思想
2021-12-05
【P1717 钓鱼】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15645444.html 题目链接 题目 话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽，为了表示安慰和鼓励，VIP999 决定请他吃一次“年年大丰收”，为了表示诚意，他还决定亲自去钓鱼。 但是，因为还要准备 NOIP2013, z老师只给了他 HHH 个小时的空余时间，假设有 nnn 个鱼塘都在一条水平路边，从左边到右编号为 1, 2, 3 … n 。 VIP是个很讲究效率的孩子，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向...
2021-11-14
【洛谷P2184 贪婪大陆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15553942.html 题目链接 题外话： 这题应该没有蓝题难度吧，就是道树状数组模板题+一些小思维 利用前缀和思想，答案很明显为 rrr 之前的区间总数- lll 之前的区间总数，即 rrr 之前的左端点数目- lll 之前的右端点数目。分别用两个树状数组维护即可。 时间复杂度 O(nlog2n)O(n\log_2n)O(nlog2n)。 1234567891011121314151617181920212223242526272829...
2022-05-24
【CF827C DNA Evolution】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16306588.html 题目链接 题目 DNA链由核苷酸组成。有四种类型的核苷酸：“A”，“T”，“G”，“C”。 DNA链是核苷酸序列。科学家决定追踪一种稀有物种的进化，它最初的DNA链为s。 物种的进化被描述为DNA的一系列变化。每个变化都是某些核苷酸的变化，例如，DNA链“AAGC”中可能发生以下变化：第二个核苷酸可以变为“T”，然后变成“ATGC”。 科学家们知道DNA链的某些片段会受到某些未知感染的影响。这些感染可以被表示为核苷酸序列...
2023-08-10
李超线段树
李超线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217504 插入过程中，先询问中点，让 uuu 在上，它必然覆盖其中一个区间。 然后看看左右端点哪里 vvv 比 uuu 大，就在对应区间递归下去