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$个数去的)

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

比如

阅读全文