tree - 范围最小值查询高于常数值

Question

给定一个包含 n 个元素的数组。找到范围 [l...r] 中元素的最小值，使得 a[k]> p 。（ l<=k<=r 和 p 随 l 和 r 而变化）。

有没有适用于 log(N) 的解决方案？

Answer 1

PS：我想到了一个解决方案来查找（k）个小于 <= p 的元素。如果数组已排序，则在范围内找到第 k+1 个元素。但是我被困在持久段树的点更新操作中，以查找第 k+1 个元素。