离线处理 RMQ

· · 个人记录

问题描述

数组 a 长度为 n，q 个询问，第 i 次询问 a 中区间 [l_i,r_i] 内的最小值。

解法

可以用单调栈处理连边，倍增走边。单次询问时间复杂度 $O(\log n)$。 考虑优化。对询问按 $l$ 从大到小排序，动态加边。则 $r$ 沿边走到最后一个位置 $p$ 上的值 $a_p$ 即为答案。这个走边的过程可以路径压缩。由于单调栈连边的特殊性，每次只会将根连边。可以证明，每次询问时只会额外路径压缩 $O(1)$ 个点，固总复杂度是 $O(n + q)$。[code](https://www.luogu.com.cn/paste/2qwwa4rf)。 证明：每次询问会遍历一条从 $r$ 到根的链，这条链会大致分为三段，从下至上依次为 存在祖先节点被路径压缩但当前段内节点都未路径压缩过的、被路径压缩过的、是新增的点还未路径压缩过的。由于之前被路径压缩的点至多有 $1$ 个，为原来路径压缩到的根节点的一个子节点，所以每次询问至多额外路径压缩 $1$ 个点（不认为原来被路径压缩到的那个根节点是被路径压缩了）。复杂度得证。