题解

核心算法

ST[j][i] 保存长度 $2^j$ 区间最小值；查询用两个可重叠块覆盖。

思路推导

min 满足幂等性，重叠元素不会改变答案。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(n log n+q)
• 空间复杂度：O(n log n)

易错点

区间长度取 floor(log2)；只适合静态查询。

完整标程见 std/main.cpp。