左偏树,可合并堆

  • O(logn)合并两个堆并维护最小或最大性质
  • 解决树上节点问题,从叶节点往根维护,每个节点看作一个堆
  • hi[x]表示到最近的叶节点的距离
  • hi[ls[x]]>=hi[rs[x]],所以每次对rs[x]合并(rs[x]树高矮)
  • hi[x]=hi[rs[x]]+1
  • fa[x]表示堆的顶点对应下标
  • 关键代码
  • static void dfs(int x){
            for(int i=head[x];i>0;i=e[i].nxt){
                int y=e[i].to;
                dfs(y);
                fa[x]=merge(fa[x],fa[y]);
            }
            while(s[fa[x]]<h[x]&&fa[x]!=0){//根据条件,删除堆顶
              //pushdown……懒标记
                fa[x]=merge(ls[fa[x]],rs[fa[x]]);
            }
    }
    static int merge(int x,int y){
            if(x==0||y==0)return x+y;
            //pushdown……
            if(s[x]>s[y]){//判定小于条件(小根堆)
                int t=x;x=y;y=t;
            }
            rs[x]=merge(rs[x],y);
            if(hi[ls[x]]<hi[rs[x]]){
                int t=ls[x];ls[x]=rs[x];rs[x]=t;
            }
            hi[x]=hi[rs[x]]+1;
            //pushup……维护子树和,子树大小……
            return x;
        }

  • 若多个指定同一节点

  • for(int i=1;i<=m;++i){
         fa[c[i]]=merge(fa[c[i]],i);//直接维护节点堆
    }
  • 因为在树上操作从叶子到根,fa[x]直接就是堆顶

  • 若是要查找指定点所在堆的堆顶,需要跳fa[x],采用路径压缩加速

  • 注意删除时对fa[x]的维护

  •  fa[ls[x]]=fa[rs[x]]=fa[x]=merge(ls[x],rs[x]);

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/655429.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

14、类与对象(采用图解方式分析内存结构)①

在idea中创建一个新文件&#xff0c;名称为Hello.java 其中&#xff0c;Hello就是一个类&#xff0c;main是这个类里面的方法&#xff0c;这意味着我们在学习的时候已经在使用类了。 对象和类 一、概念二、⭐内存分配机制分析Ⅰ、基本内存结构⭐⭐Ⅱ、调用类方法的内存分析&am…

【效率提升】Edge浏览器

现如今&#xff0c;无论是办公、学习&#xff0c;还是日常搜索、娱乐等&#xff0c;选择一个搜索快&#xff0c;准确率高&#xff0c;不卡顿&#xff0c;没广告的浏览器都是非常重要的。我想向大家推荐一款极具实力的浏览器&#xff1a;Microsoft Edge。 Microsoft Edge 浏览器…

具有固定宽度的盒子:\makebox, \parbox

makebox \makebox 是 LaTeX 中的一个命令&#xff0c;用于创建一个具有固定宽度的盒子&#xff0c;并在该盒子内放置内容。这个命令可以用于控制文本或对象的位置和对齐。 语法如下&#xff1a; \makebox[<width>][<alignment>]{<content>}其中&#xff1…

【c++leetcode】69. Sqrt(x)

问题入口 二分搜索 最困难的是能否意识到用二分搜索法解题。 算术平方根的区间在[1, x] 。代码如下&#xff1a; class Solution { public:int mySqrt(int x) {if (x 1 || x 0){return x;}int64_t start 1;int64_t end x;while (start < x){int64_t mid start (en…

HttpClient cookie爬虫记录

记录一次java语言使用httpclient爬取网站接口数据的经历 需要用到的依赖&#xff1a; httpclient和httpcore是封装了http请求的工具类 jsoup可以将返回的网页html找到你需要的xml节点&#xff0c;很方便 <dependency><groupId>org.apache.httpcomponents</gr…

Raven2掠夺者2渡鸦2游戏预约注册教程 账号注册教程

《渡鸦2》是一款源自韩国的创新力作&#xff0c;作为《Raven》系列的最新续篇&#xff0c;这款游戏在MMORPG手游领域内再度扩展了其标志性的暗黑奇幻宇宙&#xff0c;融入了大量革新的游戏设计与丰富内容。定档于2024年5月29日开启公测的《渡鸦2》&#xff0c;正处在紧张刺激的…

华语电影新力量用短片讲述:一部好电影,影响深远

近日&#xff0c;上汽大众杯澳涞坞全球青年电影短片大赛的公益短片《首映》在澳门澳涞坞首映发布&#xff0c;这一作品不仅展示了电影人的真实生活&#xff0c;更深刻地传达了对华语电影的敬意以及对青年电影人的殷切期望。 短片《首映》的制作团队堪称豪华。资深导演杨枫担任…

数据结构的希尔排序(c语言版)

一.希尔排序的概念 1.希尔排序的基本思想 希尔排序是一种基于插入排序算法的优化排序方法。它的基本思想如下: 选择一个增量序列 t1&#xff0c;t2&#xff0c;......&#xff0c;tk&#xff0c;其中 ti > tj, 当 i < j&#xff0c;并且 tk 1。 按增量序列个数k&#…

HCIP的学习(25)

VLAN间通讯技术 使用多臂路由的方式 ​ 路由器的物理接口默认是不识别802.1Q标签的&#xff0c;所以&#xff0c;交换机连接路由器的接口在发送数据帧时&#xff0c;应该将标签剥离。----一般常使用Access接口配置。 单臂路由 ​ 所谓的单臂路由&#xff0c;实际上试讲路由器…

新书速览|Golang+Vue.js商城项目实战

架构师一步一步教你做项目&#xff0c;从架构设计到技术实现完整解析 本书内容 《GolangVue.js商城项目实战》以Gin和Vue.js为核心框架&#xff0c;以全栈商城项目开发为主线&#xff0c;详尽介绍前后端分离架构开发Web网站项目的关键阶段和技术细节。全书共9章&#xff0c;第…

IGMP——组播成员端网络协议

目录 一.IGMP基本概念 &#xff08;1&#xff09;组播转发困境 &#xff08;2&#xff09;感知组播成员方式 &#xff08;3&#xff09;IGMP版本 二.IGMP各版本的区别与联系 &#xff08;1&#xff09;IGMPV1 1.普遍组查询报文 2.成员关系报告报文 3.IGMPV1报文格式 4…

手撕C语言题典——返回倒数第 k 个节点(面试题)

前言 依旧力扣&#xff0c;这道题之前有做过类似的题&#xff0c;今天给一个新的思路去做&#xff0c;应对面试时候遇到的奇奇怪怪的问题 面试题 02.02. 返回倒数第 k 个节点 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/kth-node-from-end-of-list-…

display ospf routing类型字段:Transit、Stub(区域内部)与Type2

4. B 通过 display ospf routing 命令可显示本路由器中 OSPF 路由表的信息。 其中的路由条目中 &#xff0c; 包含了 到区域内与本路由器直连 (邻居 )的路由器的路由 (TypeTransit) 、 到区域内与本路由器不直连的路由器的路由 (Type-Stub) 、 到自治系统内其它区域的路由(…

Golang | Leetcode Golang题解之第103题二叉树的锯齿形层序遍历

题目&#xff1a; 题解&#xff1a; func zigzagLevelOrder(root *TreeNode) (ans [][]int) {if root nil {return}queue : []*TreeNode{root}for level : 0; len(queue) > 0; level {vals : []int{}q : queuequeue nilfor _, node : range q {vals append(vals, node.V…

Servlet跳转404(解决)

1.解决无法跳转的404问题&#xff08;最根本&#xff0c;最重要&#xff09; 查看Project Structure&#xff0c;检查你的JDK版本不要选错版本&#xff1b; 2.页面跳转&#xff0c;url栏输入的是web.xml中的url-pattern内容&#xff0c;请仔细检查 3.关于配置信息Applicatio…

jQuery下载教程

官网&#xff1a;https://jquery.com/ ** ** 点击为压缩版本 将网站打开 界面上邮件保存为js文件即可 在html文件中引入即可 <html> <head></head> <body><script src"./js/jquery-3.6.3.js"> </script> </body> <…

卧槽!这项目开源了!【送源码 】

随着科技的飞速发展&#xff0c;个人财务管理变得越来越重要。一个名为‘Maybe’的创新型个人财务与财富管理应用程序随之诞生&#xff0c;它以其丰富的功能和用户友好的界面受到了广大用户的关注。 现在项目方将这个价值 100万美元的个人理财应用项目开源了 Maybe Maybe应用…

短剧解说一键生成原创文案的快速方法

如今短剧创作火的一塌糊涂&#xff0c;它们以其简洁明了的剧情、生动有趣的角色和紧凑的节奏&#xff0c;吸引了大量观众的关注。因此&#xff0c;它所带来的流量是非常巨大&#xff0c;不少人将流量的获取瞄准了短剧创作领域以及短剧解说领域。而对于短剧解说人员来讲&#xf…

网工内推 | 高校、外企网工,IE认证优先,年薪最高18w

01 上海外国语大学贤达经济人文学院 &#x1f537;招聘岗位&#xff1a;高校网络主管 &#x1f537;职责描述&#xff1a; 1、负责总机房、网络规划及管理&#xff0c;包括容量规划、成本评估、建设管理等; 2、负责设计、实施及维护全网络架构及规划网络变更计划 3、负责网络功…

Linux下的权限

目录 1.shell命令以及运行原理 1.1原理上初步理解shell外壳 1.1.1为什么要有shell外壳 1.1.2shell外壳是什么 1.1.3怎么办&#xff08;shell外壳的基本运行原理&#xff09; 2.Linux下的用户 3.Linux权限管理 3.1.文件访问者的分类&#xff08;人&#xff09; 3.2…