查找范围内的 min(A[L], max(A[L+1], min(A[L+2],...,a[R])))

Question

给定数组 A 由 N (1 <= N <= 10^5) 个小于 10^6 的正整数组成。给定 Q (1 <= Q <= 10^5) 个查询，对于 (L, R) (1 <= L <= R <= N) 形式的每个查询，打印出：

min(A[L], max(A[L+1], min(A[L+2], ...A[R]))))

请注意，我们不取 (A[L+2], A[L+3], ..., A[R-1], a[R]) 的最小值。“Min”和“max”是交错的。

• 例如：A[10] = {3, 1, 4, 5, 5, 2, 7, 8, 1, 1} 和 1 个查询 (1, 8)：

min(A[1], max(A[2], min(A[3], max(A[4], min(A[5], max(A[6], min(A[7], A[8])))))))

= min(3, max(1, min(4, max(5, min(5, max(2, min(7, 8)))))))

= min(3, max(1, min(4, max(5, min(5, max(2, 7))))))

= min(3, max(1, min(4, max(5, min(5, 7)))))

= min(3, max(1, min(4, max(5, 5))))

=min(3, max(1, min(4, 5)))

=min(3, max(1, 4))

=min(3, 4) 

= 3

• 我的解决方案是对于每个查询，考虑所有 A[i] (L <= i <= R) 以获得结果。但这是不可能的，因为 N <= 10^5。这个问题还有其他解决办法吗？感谢大家。

Answer 1

优化此问题的一种方法是使用动态规划。

对于所有人R - L + 1 >= 3，请注意

Q(L, R) = min(A[L], max(A[L+1], Q(L+2, R))

此外，请注意，min(a, max(b, c)) = min(a, b) = a如果a <= bas max(b, c) >= b >= a. 这有助于得出这样的结论：Q(L, R) = A[L]对于所有L位置A[L] <= A[L+1]，无论的值如何R。您还可以选择使用 if 来max(a, min(b, c)) = max(a, b) = a为（并因此） ifa >= b得出类似的结论。max(A[L+1], Q(L+2, R))Q(L, R)A[L] > A[L+1] >= A[L+2]