P1081

题目简述

有一排高低不同的城市 城市距离=高度差

A和B自左向右开车旅行(出发点可以变)

A、B的开车风格:

1.A会前往右边距他第二近的城市
2.B会前往右边最近的城市
3.A和B开过的总里程不超过$X$

询问:

1.给定一个$X$ 求出从哪个城市出发 $A$的路程/$B$的路程 最大

2.给定$X_i$和出发城市$S_i$ 求$A$和$B$分别开的距离数

倍增

在没有修改的RMQ问题(区间最值问题) 基于倍增的ST表可以做到$O(1)$查询和$O(nlogn)$预处理

拿最大值来说我们用$Max[i][j]$表示,从$i$位置开始的$2^j$个数中的最大值,例如$Max[i][1]$表示的是$i$位置和$i+1$位置中两个数的最大值(也就是说当前位置是被包含进$2^j$个数去的)

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值

比如

阅读全文

学习了 LCA(最近公共祖先) 这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。

什么是LCA

LCA就是LCA
就是求一棵树上两个节点最近的公共祖先,那么有什么用呢,用来做题。

LCA的实现

这里用到了“爬树”的方法找
例如两个节点$x,y$:
规定$deepth_x>deepth_y$
1.让深的那个节点,$x$往树上爬,直到$deepth_x = deepth_y$;
2.让两个节点一起向上跳,如果碰在一起了,那么就找到了。
嗯,真是生动形象好理解呢!

阅读全文