algorithm - (可能)一个线段树应用

Question

我已经考虑了几个小时，但我无法取得太大进展。它是这样的:

You have an array of size n and q queries. Each query is of the form (l, r, k). The answer to each query is the index (1-based) of the leftmost number in the range [l, r] which is greater than or equal to k. If there is no such value, return -1. Constraints: n, q <= 1e5, l <= r and the elements can be from 0 to 1e9. The program should run within a second.

Example input :

n = 5, q = 2
7 4 6 9 
Queries :
3 4 7 
2 4 5
Output:
4
3

我觉得这里可以使用最大线段树，但我无法将其组合在一起。请帮忙。显然，复杂度为 O(n^2) 的解决方案无法及时运行。

Answer 1

首先构建最大线段树。这可以在 O(nlogn) 中完成。这将为我们提供一个函数 get_max(l, r)，它给出索引 l 和 r 之间的最大数，在 O(logn )。让我们调用所需的查询函数 query(l, r, k)。原始数组是arr。

query(l, r, k) {
    if(l == r) {
        if(arr[l] >= k) {
            return l;
        }
        else {
            return -1;
        }
    }
    else {
        int mid = (l + r) / 2;
        if(get_max(l, mid) >= k) {
            return query(l, mid, k);
        }
        else {
            return query(mid + 1, r, k);
        }
    }
}

这应该取 每次查询的时间。