P3793

# P3793 由乃救爷爷 题解 首先分块，对于每一个块维护一个最小值，这样是 $m\sqrt n$ 的，无法通过此题。 考虑优化分块，注意到数据是随机的所以如果 $l, r$ 在同一个块里面，可以直接暴力，均摊 $O(1)$。 > 证明： $l, r$ 在同一个块内的概率是 $\frac{1}{\ ......