GoldenPotato137的小屋

左偏树
左偏树

[Luogu P1552] [APIO2012]派遣

题面 APIO2012 派遣 Solution 这是一道左偏树的模板题,不会左偏树的可以戳这里 显然,我们可以发现对于同一颗子树,我们想让取的人尽可能便宜,如果说目前为止取的价格超过$C$,就优先把贵的人先丢掉。 因此,我们考虑用左偏树来维护这个东西。对于每一个人,我们都建一颗以价格为关键字的大根堆。考虑从下往上合并,一旦堆的元素总和超过$C$就不断弹栈,弹到合法为止。然后我们算一下$l_i*sum$,取个最大值就好。 时间复杂度$O(nlogn)$ 就酱,我们就可以把这道题切掉啦(ノ゚∀゚)ノ Code //Lu…

2019年3月15日 0条评论 686点热度 1人点赞 GoldenPotato137 阅读全文
左偏树

[Luogu P1110] [ZJOI2007]报表统计

题面 洛谷P1110 Solution 我们看到这道题,我们不妨想把处于同一个点的骑士全部丢到一个小根堆左偏树里面。这样子,我们从下往上合并,合并完就去检查一下根是否满足当前城市的要求,一直弹根弹到满足要求为止。 至于能力的变化,这里的操作要求无外乎乘法和加法。因此,我们可以像线段树II那道题那样做两个标记,处理一下即可。每次合并、弹根之前都pushdown标记。 就酱,这题就被我们切掉啦~(*´゚∀゚`)ノ 时间复杂度$O(nlogm)$ Code 数据生成器 #include<iostream> #…

2019年3月8日 0条评论 677点热度 2人点赞 GoldenPotato137 阅读全文
学习笔记

可并堆(左偏树)学习笔记

为什么要学左偏树 有时候,某些题目要求我们合并两个堆。 合并两个堆,大家都知道可以用splay暴力启发式合并处理。很不幸的是,这玩意的复杂度是$O(nlog^2n)$的,在一些毒瘤题目专门考可并堆的题目中,是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法,她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面意思一样,是一颗向左“偏”的树。什么叫“向左偏”呢?我们知道,平衡树的时间复杂度比二叉查找树优秀,是因为平衡树的左右子树深度尽…

2019年3月5日 0条评论 741点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 1 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 1 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号