(RMQ版)LCA注意要点

时间:2022-09-22 21:18:51
 inline int lca(int x,int y){    if(x>y)    swap(x,y);
return (h[rmq[log[y-x+]][x]]<h[rmq[log[y-x+]][y-near[y-x+]+]])?
rmq[log[y-x+]][x]:rmq[log[y-x+]][y-near[y-x+]+];}

查询代码如上

     build(,);
for(int i=;i<=N;i++)
rmq[][i]=list[i];
for(int i=,j=,k=;i<=N;log[i]=j,near[i]=k,i++)
if(i>k*) j++,k*=;
for(int i=,k=;k<=N;i++,k*=)
for(int j=;j<=N-k+;j++)
rmq[i][j]=(h[rmq[i-][j]]<h[rmq[i-][j+k/]])?rmq[i-][j]:rmq[i-][j+k/];

初始化代码如上

(懒得贴build了,而且各题目有所不同)

在build中,每次到一个点的时候记录一下,每找完一个儿子再记录一次


容易写错的点(也就我这种蒟蒻才会写错这么简单的东西吧)

1.找的时候找的是pos,不要用原数

2.初始化的时候k永远大于等于i/2小于i

3.比较的是h,返回的是rmq(这个不是很容易错)

一定要分清原数和dfs序的关系

都是细节,每次都在调这种东西

(RMQ版)LCA注意要点的更多相关文章

  1. 【RMQ】洛谷P3379 RMQ求LCA

    题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先. 输入输出格式 输入格式: 第一行包含三个正整数N.M.S,分别表示树的结点个数.询问的个数和树根结点的序号. 接下来N-1行每 ...

  2. RMQ求LCA

    题目链接 rmq求LCA,interesting. 一直没有学这玩意儿是因为CTSC的Day1T2,当时我打的树剖LCA 65分,gxb打的rmq LCA 45分... 不过rmq理论复杂度还是小一点 ...

  3. BZOJ1906树上的蚂蚁&amp&semi;BZOJ3700发展城市——RMQ求LCA&plus;树链的交

    题目描述 众所周知,Hzwer学长是一名高富帅,他打算投入巨资发展一些小城市. Hzwer打算在城市中开N个宾馆,由于Hzwer非常壕,所以宾馆必须建在空中,但是这样就必须建立宾馆之间的连接通道.机智 ...

  4. poj 1330 Nearest Common Ancestors(LCA 基于二分搜索&plus;st&amp&semi;rmq的LCA)

    Nearest Common Ancestors Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 30147   Accept ...

  5. dfs序&plus;RMQ求LCA详解

    首先安利自己倍增求LCA的博客,前置(算不上)知识在此. LCA有3种求法:倍增求lca(上面qwq),树链剖分求lca(什么时候会了树链剖分再说.),还有,标题. 是的你也来和我一起学习这个了qwq ...

  6. RMQ和LCA

    RMQ(Range Minimum/Maximum Query),即区间最值查询 查询很多的时候求[l,r]的最大值可以弄一个数组f[i,j]表示i~j的最大值 //这个是线段树 rmq是f[i,j] ...

  7. 数据结构 《18》----RMQ 与 LCA 的等价性 &lpar;一&rpar;

    前言     RMQ: 数组 a0, a1, a2,..., an-1, 中求随意区间 a[i+1], a[i+2], ..., a[i+k] 的最小值     LCA: 求二叉树中两个节点的最低公共 ...

  8. LOJ&num;137&period; 最小瓶颈路 加强版&lpar;Kruskal重构树 rmq求LCA&rpar;

    题意 三倍经验哇咔咔 #137. 最小瓶颈路 加强版 #6021. 「from CommonAnts」寻找 LCR #136. 最小瓶颈路 Sol 首先可以证明,两点之间边权最大值最小的路径一定是在最 ...

  9. hdu 2586 欧拉序&plus;rmq 求lca

    题意:求树上任意两点的距离 先说下欧拉序 对这颗树来说 欧拉序为 ABDBEGBACFHFCA 那欧拉序有啥用 这里先说第一个作用 求lca 对于一个欧拉序列,我们要求的两个点在欧拉序中的第一个位置之 ...

随机推荐

  1. 移动端 css实现自适应正圆 &lpar; 宽高随着手机屏幕宽度自适应 &rpar;

    序言:应朋友要求随手写了一下移动端 css实现自适应正圆 ( 宽高随着手机屏幕宽度自适应 ) ,以备后用 LESS代码: .adaptive-circle { margin: 50px auto 0; ...

  2. win7 64位安装redis 及Redis Desktop Manager使用

    写基于dapper的一套自动化程序,看到 mgravell的另一个项目,StackExchange.Redis,之前在.NET上用过一段时间redis,不过一直是其它的驱动开发包,这个根据作者介绍,是 ...

  3. 深度学习研究理解5:Visualizing and Understanding Convolutional Networks(转)

    Visualizing and understandingConvolutional Networks 本文是Matthew D.Zeiler 和Rob Fergus于(纽约大学)13年撰写的论文,主 ...

  4. confirm使用方法

    定义和使用方法 confirm() 方法用于显示一个带有指定消息和 OK 及取消button的对话框. 语法 confirm(message) 參数 描写叙述 message 要在 window 上弹 ...

  5. windows phone &lpar;14&rpar; 简单了解Ellipse元素和Rectangle元素

    原文:windows phone (14) 简单了解Ellipse元素和Rectangle元素  System.Windows.Shapes命名空间中包含了显示矢量图形的元素分别为ellipse和re ...

  6. 第一百零六节,JavaScript变量作用域及内存

    JavaScript变量作用域及内存 学习要点: 1.变量及作用域 2.内存问题 JavaScript的变量与其他语言的变量有很大区别.JavaScript变量是松散型的(不强制类型)本质,决定了它只 ...

  7. javascript如何自动去除所有空格?

    1.jquery自带了trim方法:    $.trim(" abc ") // abc 2.自己写方法: function trim(str) { return str.repl ...

  8. 第二周 数据分析之展示 Matplotlib基础绘图函数实例

    Pyplot基础图表函数 Pyplot饼图的绘制: Pyplot直方图的绘制: Pyplot极坐标图的绘制: Pyplot散点图的绘制: 单元小结: import numpy as np import ...

  9. 通过mycat实现mysql的读写分离

    mysql的主从配置沿用上一篇博客的配置:https://www.cnblogs.com/MasterSword/p/9434169.html mycat下载地址:http://www.mycat.i ...

  10. 本地代码上传到githup

    1.githup网站创建new repository 2.执行下面命令,找到本地用户公钥地址 ssh -v git@github.com 输出: debug1: Offering RSA public ...