四毛子

头好乱，不知道能干什么，心里好难受。

做题做不进去，颓废不能颓，所以学学新算法。

考虑如何解决静态区间差值为 \(1\) 最值问题。

首先分块，\(B = \lceil \frac{log_2 n}{2} \rceil\)。

整块怎么做，直接用 \(st\) 表，空间是 \(O(n)\) 的，散块预处理前后缀就好了。

询问落进同一个区间这么做。

注意到单个块的形状只有 \(s^{B-1}\) 种，而每种块的子区间最值是一定的。

所以对每一种块预处理出来即可。

预处理时间复杂度 \(O(n)\)，回答 \(O(1)\)。

如何解决差值不为 \(1\) 的。
转化为笛卡尔树，变成求两点的 \(lca\)，接着就是 \(dep\) 的区间最值，满足上一个问题。