最新要闻
- 左偏树-环球观点
- 世界最新:ChatGPT只讲这25个笑话!有90%重复 网友:幽默是人类最后的尊严
- 环球速讯:火车站按摩椅现大量虫子 商家:每天都有打扫 很少有这种情况
- 焦点滚动:福建多地为何纷纷成立这一机构?
- 聚焦:希捷4TB机械硬盘史低 仅售288元
- 社交综艺为何能成爆款_世界百事通
- 芯片的战争
- 这些年,祝勇的“纸上故宫”都在写些什么?|文化观察 天天讯息
- 吢丕的另一个情侣网名(吢)
- 环球短讯!最后一艘潜艇电影国语版百度云(最后一艘潜艇电影国语版)
- 镁条在空气中燃烧发出耀眼的白光(镁条在空气中燃烧)
- 女朋友不理你怎么办表情包_女朋友不理你怎么办
- 南京两大厦间现龙卷风:强风至路面闪现火花 每日视点
- 当前简讯:14代酷睿要来了 英特尔13代酷睿i9包装简化:独特身份消失
- 预计2025年突破万亿元规模 产学研各方共议储能大赛道
- 徐州城下城遗址博物馆“上新”
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
左偏树-环球观点
左偏树是一种可以让我们在 \(O(\log n )\) 的时间复杂度内进行合并的堆式数据结构。
为了方便以下的左偏树为小根堆来讨论。
(资料图片)
定义外结点:左儿子或者右儿子是空节点的结点。
距离:一个结点 \(x\) 的距离 \(dis[x]\) 定义为其子树中与结点 \(x\) 最近的外结点到 \(x\) 的距离。定义空节点的距离为 \(-1\)。
性质左偏树具有堆性质,即若满足小根堆的性质,则对于每一个结点 \(x\),都有 \(w[x]\le w[ls[x]],w[x]\le w[rs[x]]\)。其中 \(w\) 为权值,\(ls,rs\) 为左儿子,右儿子。
左偏树具有左偏的性质,即对于每一个点 \(x\),都有 \(dis[ls[x]]\ge dis[rs[x]]\)。
基本结论结点 \(x\) 的距离 \(dis[x]=dis[rs[x]]+1\),很明显上面说过的性质里面可以看出右儿子的距离更小,所以我们在计算当前结点的 \(dis\) 时应该用更小的 \(dis[rs]\)。
距离为 \(n\) 的左偏树至少有 \(2^{n+1}-1\) 个结点,此时该左偏树的形态是一棵满二叉树。
操作合并左偏树的很多操作都是需要用到合并操作的。
我们用 merge(x,y)
来表示合并两棵以 \(x,y\) 为根节点的左偏树,其返回值就是合并之后的根节点的编号。
首先如果要是不考虑左偏的性质,假设我们合并的是小根堆:
若 \(w[x]\le w[y]\),以 \(x\) 作为合并后的根节点;否则以 \(y\) 作为合并后的根节点。为了避免讨论,若有 \(w[x]>w[y]\) 我们就 swap
一下。
将 \(y\) 与 \(x\) 的其中一个儿子合并,用合并后的根节点代替与 \(y\) 合并的儿子的位置,并返回 \(x\)。
重复以上操作,如果 \(x,y\) 有一个是 \(0\),就返回 \(x+y\),也就是返回不为 \(0\) 的结点的编号。
当然上述的方法在数据为一条链的时候会 T 飞,所以我们需要让他左右保持一个相对平衡的状态,这个时候我们就有了左偏树(当然平衡树也可以)。
由于我们前面说过左偏树中左儿子的距离大于右儿子的距离,我们每次将 \(y\) 与 \(x\) 的右儿子合并,由于左偏树的树高为 \(\log n\) 的,所以单次合并的复杂度也为 \(O(\log n)\)。
但是,两棵左偏树按照上述方法合并后,可能不再保持左偏树的左偏性质。在每次合并完之后,判断对结点 \(x\) 是否有 \(dis[ls[x]]\ge dis[rs[x]]\),若没有则交换 \(ls,rs\),并维护 \(x\) 的距离 \(dis[x]=dis[rs[x]]+1\),即可维护左偏树的左偏性质。
插入给定值我们可以直接新建一个点,然后将他和左偏树合并就好。
求最小(大)值由于满足堆的性质,所以我们直接返回堆顶的元素就好。
删除最小(大)值也就是删除堆顶元素,直接合并根节点的左右儿子即可。
删除任意结点inline void del(int x){int tmp=merge(ls[x],rs[x]),fu=fa[x];f[tmp]=fa[tmp]=fu;f[x]=fa[x]=tmp;ls[fu]==u?ls[fu]=tmp:rs[fu]=tmp;while(fu){if(dis[ls[fu]]
这里 \(fa\) 是父节点。
我们和删除根节点一样先合并子树,然后存起来删除的点的父节点 \(fu\)。
然后合并后的点的父节点和所属点先设为 \(fu\),然后我们把删除了的给调整成父节点和所在左偏树根节点为合并后的结点。
然后判断删除的点是父节点的左儿子还是右儿子然后用合并后的替换。
然后我们从父节点不断向上更新 \(dis\) 并用 swap
来维护左偏性质即可。
我们可以开个数组 \(f\) 来记录父节点然后每次询问暴力跳,但是复杂度太高。
我们思考一下,我们可以像并查集一样采用路径压缩的办法来让这个复杂度变低。
在合并两个结点的时候,令 f[x]=f[y]=merge(x,y)
。
在删除左偏树中的最值时,我们令 f[ls[x]]=f[rs[x]]=f[x]=merge(x,y)
,因为 \(x\) 是之前左偏树的根节点,在路径压缩的时候可能有 \(f\) 的值等于 \(x\),所以 \(f[x]\) 也要指向删除后的根结点。
【模板】左偏树(可并堆) - 洛谷
code:
#include#define int long long#define N 1000100using namespace std;int n,m,ls[N],rs[N],dis[N],f[N],vis[N];struct sb{int id,w;bool operator<(sb x)const{return w==x.w?id>n>>m;for(int i=1;i<=n;i++) cin>>e[i].w,f[i]=i,e[i].id=i;for(int i=1;i<=m;i++){int op,x,y;cin>>op;if(op==1){cin>>x>>y;if(vis[x]||vis[y])continue;int xx=fid(x),yy=fid(y);if(xx==yy)continue;f[xx]=f[yy]=merge(xx,yy);}else{cin>>x;if(vis[x]){puts("-1");continue;}int xx=fid(x);cout<
参考:https://www.luogu.com.cn/blog/hsfzLZH1/solution-p3377
关键词:
左偏树-环球观点
世界最新:ChatGPT只讲这25个笑话!有90%重复 网友:幽默是人类最后的尊严
环球速讯:火车站按摩椅现大量虫子 商家:每天都有打扫 很少有这种情况
焦点滚动:福建多地为何纷纷成立这一机构?
聚焦:希捷4TB机械硬盘史低 仅售288元
社交综艺为何能成爆款_世界百事通
芯片的战争
这些年,祝勇的“纸上故宫”都在写些什么?|文化观察 天天讯息
List 接口及其常用方法 全球即时看
文心一言 VS 讯飞星火 VS chatgpt (38)-- 算法导论5.4 2题 全球新要闻
吢丕的另一个情侣网名(吢)
环球短讯!最后一艘潜艇电影国语版百度云(最后一艘潜艇电影国语版)
镁条在空气中燃烧发出耀眼的白光(镁条在空气中燃烧)
女朋友不理你怎么办表情包_女朋友不理你怎么办
南京两大厦间现龙卷风:强风至路面闪现火花 每日视点
当前简讯:14代酷睿要来了 英特尔13代酷睿i9包装简化:独特身份消失
预计2025年突破万亿元规模 产学研各方共议储能大赛道
徐州城下城遗址博物馆“上新”
天天热点!金陵十二钗判词及人物(金陵十二钗判词)
每日消息!散水模板工程量怎么计算(算混凝土工程量散水怎么计算)
今日快讯:口腔材料app(口腔材料网)
焦点热议:好高骛远的读音_好高骛远的意思
今日热议:Hbase安装和shell客户端操作
Web安全-渗透测试-信息收集01|全球热文
世界热消息:杯具!上海一小区电动车爆炸起火 家人惨被烧伤:网友吵翻为何电池拿回家充电
莫扎特的一句话(关于莫扎特的话例如说他天真)
世界热点!莫扎特的一句话(关于莫扎特的话例如说他天真)
清远公用品牌IP形象亮相-全球播报
关于铁路计次票、定期票 如何购买使用 环球聚看点
天天视点!多地高温预警 今年618空调没促销降价:还有经销商趁机涨价
龙爸无双100集电视剧免费观看|当前热门
第二届联合国人居大会闭幕 通过“人人享有可负担住房”等决议_百事通
消息!第二届联合国人居大会闭幕 通过“人人享有可负担住房”等决议
中超综合:中超第一阶段结束 上海海港领跑积分榜
中超积分榜:海港领跑三镇仅第8 大连人倒数第一
第34届中国经济新闻奖:21世纪经济报道获评论一等奖、融合报道一等奖 天天精选
全球讯息:武汉到清江画廊旅游攻略_清江画廊旅游攻略
新动态:最美童星长大后惊艳全网!16岁时因“不够性感”被导演刷掉,她霸气怒怼:恶心的猪!
窒息灭火法是指什么_窒息灭火法
全球快资讯:美国旧金山毒品泛滥、暴力犯罪猖獗 市民称正在目睹西方文明崩溃
每日热门:引导资金支持绿色发展 新华碳科技指数发布
这些大胆的古早综艺,真的是不付费就能看的吗? 当前消息
《暗黑破坏神4》差评如潮 跌到5.1分了_世界焦点
最资讯丨蓉火传递启动|“中国民航英雄机组”成员毕楠:当上火炬手,是荣誉也是责任
社区多元化多角度全方位服务新业态新就业群体
以太阳鸟为标志 G985高铁列车因高考火了:网友打卡沾喜气
湖南景区回应游客漂流翻船:第一天开业人多 放水没控制好-即时看
每日一猜6月10日:哪款能重塑眼镜人士新体验 世界快播
热点在线丨7744小游戏盒_7743小游戏
北京铁路:6月15日起,京津城际、京唐城际等线路运行图有调整
五部门联合启动河湖安全保护专项执法行动
全球信息:21个“问界”商标已转让至华为 申请时间为今年3月
9成产品“赚到钱”!部分债基开始限购
每日一猜6月10日:哪款能重塑眼镜人士新体验
上海一兆韦德倒闭_上海一兆韦德团购
大金鼠:你生在冬天还是春天?出生的季节决定财富! 天天新消息
111ttt舞曲网交谊舞曲_111ttt要听舞曲网每天都要听
【世界新视野】投资超2.5亿 电影《红海行动2》正式启动:比肩《战狼》的动作大片
环球快讯:相机功能也开始付费了:理光K-3 Mark III新功能需付费解锁
Zen3游戏神器 AMD锐龙5 5600X3D曝光:售价只要1000多?
杨尚琨简历_万绍芬与杨尚琨关系
天天热资讯!古曲100首经典_古曲
当前热点-淮安多措并举做好“三夏”服务工作
NGINX配置详解
【技术积累】SpringBoot中的简介与配置【一】
龙爸无双100集电视剧免费观看|环球热点评
装饰材料包括什么东西(装饰材料都包括什么) 环球即时看
微软Edge离奇改动:新版不再支持删除云端同步数据
《变形金刚》《蜘蛛侠》不分伯仲:2023暑期档票房破10亿_世界播资讯
乳晕变大是怎么回事(乳晕大怎么回事)-天天热点
证监会就公开募集证券投资基金投资顾问业务管理规定公开征求意见_每日简讯
陕西西安推动“十里沣河”文旅深度融合古老沣河涌动新活力 焦点资讯
低价团乱象再起 何以无解?|头条焦点
四川省社科院周友苏:适合且能推动上市公司高质量发展的规章制度才是“良法善治”|世界短讯
【世界播资讯】【技术积累】Python中的Pandas库【三】
Linux命令篇 - tar 命令
瑞虎8保养灯怎么消除(本田冠道保养灯怎么消除?) 环球速递
王永调研阿洛亚与蜜泉湖联通工程时强调:树立“大景区、大旅游”理念 努力打造全域旅游胜地|每日速递
天天要闻:日本人拆了辆比亚迪海豹 还出了本书 定价6.7万
你买过“游戏盘”么?分析师:无实体游戏将在2028年成主流|资讯
居理买房暴雷!前员工称“欠薪千万元,丈母娘顶替法人” 全球观焦点
ps保存不了jpg格式怎么办(ps保存不)
惩治网暴,公检法三部门公开征求意见!维权难度能降低吗?
湖南博物馆千年古尸_湖南博物馆千年女干尸|焦点关注
焦点速讯:问麻了…阿里一面索命27问,过了就60W+
世界通讯!小迪网安笔记二:信息收集
极目时评丨环卫母亲与高考儿子相拥而泣刷屏,普通人改变命运的努力打动人心
坚守“可靠”坦克Hi4-T 当下新能源越野的更优解 世界播报
当前聚焦:遗体告别仪式流程和掩口流程(遗体告别仪式流程)
国家防总启动防汛四级应急响应,派工作组赴广西福建指导救灾
手机充电很慢是怎么回事呢_手机充电很慢
《猎魔人》S3新预告再惹观众怒火 服装造型太糟糕-当前热闻
我是大运火炬手丨第一棒火炬手邹敬园:我在成都等你们
打新套利动辄千万,“万人摇”乱象丛生,楼市限价将“退出”? 今日热议
西安艺术高级中学网站(西安艺术高级中学)
天津滨海新区可提供伊立浦电压力锅维修服务地址在哪 全球今热点
全球讯息:化疗的时候有什么症状(化疗是什么感觉)
当你变成兔子中文在线玩_当你变成兔子
Maven常用命令及其作用_全球速读
tab是什么意思英语_tab是什么意思-天天报道