左偏树 & 可并堆
左偏树\可并堆
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132507434
https://www.luogu.com.cn/problem/P3377
作用：可并堆
形态：堆+满二叉树
即左节点最小深度大于等于右节点最小深度
合并过程：
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-02-15
【一本通OJ 1603：绿色通道】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15897506.html 题目链接 题目 高二数学《绿色通道》总共有 nnn 道题目要抄，编号 1…n1\ldots n1…n，抄第 iii 题要花 aia_iai 分钟。小 Y 决定只用不超过 ttt 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。 现在，小 Y 想知道他在这 ttt 分钟内写哪...
2023-12-19
势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446
势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093792 https://www.luogu.com.cn/problem/P7446 https://www.luogu.com.cn/problem/CF1491H 看到题，发现只有减，就和势能有关。维护势能，像这种题，树形ds显然不好做，所以可以去考虑进行分块。 考虑分块。每个块记录一个 bib_ibi ， iii 的...
2024-09-11
[SCOI2014] 方伯伯的玉米田（DP+树状数组维护行列）
[SCOI2014] 方伯伯的玉米田（dp+树状数组维护行列） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142137107 https://www.luogu.com.cn/problem/P3287 显然每次操作的区间一定是一个后缀 我们直接令 dp(x,i)dp(x,i)dp(x,i) 表示最后一个数是 xxx （加之后），加了 iii 次的最长长度，转移显然 maxdp(y≤x,j≤i)\max dp(y\le x, j\le i)maxdp(...
2021-11-18
【P2344 [USACO11FEB]Generic Cow Protests G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接 首先朴素dp不用讲，设 dpidp_idpi 表示前 iii 个数划分的总方案数，SiS_iSi 表示前 iii 个数的和。 dpi=∑j=0i−1dpj (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi=j=0∑i−1dpj(Si−Sj⩾0) 其中 dp0=1dp_0=1dp0=1。 可是这样的时间复杂度为 O...
2023-12-18
上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果
上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070831 https://www.luogu.com.cn/problem/P8518 没有要求在线，显然离线（。维护时间戳，上线段树。 好了，我们现在知道一个人的曲线变化了。怎么做呢？ 前面所有碰上下界的都是没用的！我们只需要找最后一段的时间段满足差值为 cic_ici 即可。因为差值更大的我们显然可以最后又会规约成这种情况...
2021-11-24
【P1270 “访问”美术馆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=maxy∈xmaxi=0smaxj=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...