左偏树 & 可并堆
左偏树\可并堆
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132507434
https://www.luogu.com.cn/problem/P3377
作用：可并堆
形态：堆+满二叉树
即左节点最小深度大于等于右节点最小深度
合并过程：
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2026-10-02
推性质 + 很多个DS：ICPC2025西安A
推性质 + 很多个DS：ICPC2025西安A Azalea Garden - Problem - QOJ.ac 我们考虑 aaa 最大的那个人 iii，显然除了它自己本身，所有 bj≤aib_j\le a_ibj≤ai 一定可以被杀死，所有 bj>aib_j>a_ibj>ai 一定杀不死 因此问题就剩下一个，它自己能不能被杀死？ bi>aib_i>a_ibi>ai 显然不能 接下来，我们考虑所有 bj>aib_j>a_ibj>ai 的生物，它们显然最后会一直存活。考虑它们当中 aaa 的最大值 AAA 如果 A...
2023-08-10
点分治小结
点分治小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治 找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案 注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...
2023-08-29
动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B
动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132566345 https://www.luogu.com.cn/problem/CF1192B 对于直径的求法，常用dp或两次dfs，但如果要动态维护似乎都不太方面，那么可以维护树上路径最大值。 树上路径为： depu+depv−2×deplca(u,v)dep_u+dep_v-2\times de...
2023-08-10
点分治过程中维护李超线段树：CF1303G
点分治过程中维护李超线段树：CF1303G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132219909 https://www.luogu.com.cn/problem/CF1303G 看到这题，首先很容易想到树形dp，但发现要维护两个值，一个为末项，一个为和，很好分析出这个东西有凸性。 这个时候有两种做法，维护凸包或李超线段树。 之所以用李超线段树，是可以想象出维护末项（k）和和 （b）之后最终的答案其实之和队对面的深度（x）有关，而这个大胆猜测可以...
2022-02-16
【一本通OJ 1600：【例 4】旅行问题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15901652.html 题目链接 题目 原题来自：POI 2004 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：判断以每个车站为...
2026-10-17
dp+线段树+单调栈：ABC480G
dp+线段树+单调栈：ABC480G G - Zonal Score Minimization 设 fif_ifi 表示前 iii 个数的满足题意的答案 显然有： fi=minj≤i−1(fj+mink∈[j+1,i]ak−maxk∈[j+1,i]ak)f_i=\min_{j\le i -1}(f_j+\min_{k\in[j+1,i]}a_k-\max_{k\in[j+1,i]}a_k) fi=j≤i−1min(fj+k∈[j+1,i]minak−k∈[j+1,i]maxak) 我们考虑拿数据结构来维护。后缀min、max之类的我们可以直接拿单调栈来求，然后拿个...