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注意要点的更多相关文章
-
【RMQ】洛谷P3379 RMQ求LCA
题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先. 输入输出格式 输入格式: 第一行包含三个正整数N.M.S,分别表示树的结点个数.询问的个数和树根结点的序号. 接下来N-1行每 ...
-
RMQ求LCA
题目链接 rmq求LCA,interesting. 一直没有学这玩意儿是因为CTSC的Day1T2,当时我打的树剖LCA 65分,gxb打的rmq LCA 45分... 不过rmq理论复杂度还是小一点 ...
-
BZOJ1906树上的蚂蚁&;BZOJ3700发展城市——RMQ求LCA+树链的交
题目描述 众所周知,Hzwer学长是一名高富帅,他打算投入巨资发展一些小城市. Hzwer打算在城市中开N个宾馆,由于Hzwer非常壕,所以宾馆必须建在空中,但是这样就必须建立宾馆之间的连接通道.机智 ...
-
poj 1330 Nearest Common Ancestors(LCA 基于二分搜索+st&;rmq的LCA)
Nearest Common Ancestors Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 30147 Accept ...
-
dfs序+RMQ求LCA详解
首先安利自己倍增求LCA的博客,前置(算不上)知识在此. LCA有3种求法:倍增求lca(上面qwq),树链剖分求lca(什么时候会了树链剖分再说.),还有,标题. 是的你也来和我一起学习这个了qwq ...
-
RMQ和LCA
RMQ(Range Minimum/Maximum Query),即区间最值查询 查询很多的时候求[l,r]的最大值可以弄一个数组f[i,j]表示i~j的最大值 //这个是线段树 rmq是f[i,j] ...
-
数据结构 《18》----RMQ 与 LCA 的等价性 (一)
前言 RMQ: 数组 a0, a1, a2,..., an-1, 中求随意区间 a[i+1], a[i+2], ..., a[i+k] 的最小值 LCA: 求二叉树中两个节点的最低公共 ...
-
LOJ#137. 最小瓶颈路 加强版(Kruskal重构树 rmq求LCA)
题意 三倍经验哇咔咔 #137. 最小瓶颈路 加强版 #6021. 「from CommonAnts」寻找 LCR #136. 最小瓶颈路 Sol 首先可以证明,两点之间边权最大值最小的路径一定是在最 ...
-
hdu 2586 欧拉序+rmq 求lca
题意:求树上任意两点的距离 先说下欧拉序 对这颗树来说 欧拉序为 ABDBEGBACFHFCA 那欧拉序有啥用 这里先说第一个作用 求lca 对于一个欧拉序列,我们要求的两个点在欧拉序中的第一个位置之 ...
随机推荐
-
移动端 css实现自适应正圆 ( 宽高随着手机屏幕宽度自适应 )
序言:应朋友要求随手写了一下移动端 css实现自适应正圆 ( 宽高随着手机屏幕宽度自适应 ) ,以备后用 LESS代码: .adaptive-circle { margin: 50px auto 0; ...
-
win7 64位安装redis 及Redis Desktop Manager使用
写基于dapper的一套自动化程序,看到 mgravell的另一个项目,StackExchange.Redis,之前在.NET上用过一段时间redis,不过一直是其它的驱动开发包,这个根据作者介绍,是 ...
-
深度学习研究理解5:Visualizing and Understanding Convolutional Networks(转)
Visualizing and understandingConvolutional Networks 本文是Matthew D.Zeiler 和Rob Fergus于(纽约大学)13年撰写的论文,主 ...
-
confirm使用方法
定义和使用方法 confirm() 方法用于显示一个带有指定消息和 OK 及取消button的对话框. 语法 confirm(message) 參数 描写叙述 message 要在 window 上弹 ...
-
windows phone (14) 简单了解Ellipse元素和Rectangle元素
原文:windows phone (14) 简单了解Ellipse元素和Rectangle元素 System.Windows.Shapes命名空间中包含了显示矢量图形的元素分别为ellipse和re ...
-
第一百零六节,JavaScript变量作用域及内存
JavaScript变量作用域及内存 学习要点: 1.变量及作用域 2.内存问题 JavaScript的变量与其他语言的变量有很大区别.JavaScript变量是松散型的(不强制类型)本质,决定了它只 ...
-
javascript如何自动去除所有空格?
1.jquery自带了trim方法: $.trim(" abc ") // abc 2.自己写方法: function trim(str) { return str.repl ...
-
第二周 数据分析之展示 Matplotlib基础绘图函数实例
Pyplot基础图表函数 Pyplot饼图的绘制: Pyplot直方图的绘制: Pyplot极坐标图的绘制: Pyplot散点图的绘制: 单元小结: import numpy as np import ...
-
通过mycat实现mysql的读写分离
mysql的主从配置沿用上一篇博客的配置:https://www.cnblogs.com/MasterSword/p/9434169.html mycat下载地址:http://www.mycat.i ...
-
本地代码上传到githup
1.githup网站创建new repository 2.执行下面命令,找到本地用户公钥地址 ssh -v git@github.com 输出: debug1: Offering RSA public ...