sas's blog

Nearest greater element
By sas, history, 7 years ago, In English

The problem is: given an array of size n(n < 2 * 10 ^ 5) of integers(a[i] < 2 * 10 ^ 5) and 2 types of queries. The first one is to assign a value to an element(v < 2 * 10 ^ 5), another is to find such minimal k that k >= i and a[k] >= x(i and x are given and lesser than 2 * 10 ^ 5 both). I wonder how to solve it faster than O(nlog^2(n)).

  • Vote: I like it
  • -22
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

You can solve it in NlogN about the same way you solve it in Nlog^2. You keep a segment tree with the maximum on each segment, and then when you need a certain position you can instead of binary searching it, go directly to it through the intern structure of the segment tree. For example, let's consider how the interval [i, N] is decomposed in at most logN intervals maintained in the segment tree, in order of their appearance. Now, you can iterate over them: the position you're looking for is part of the first segment with a maximum value of at least how much you need (that is x). So far you had O(logN). Now all you have to do is to find the first position in this interval with value greater than x (such a position exits as the maximum would be fine — we already checked that). So you can go downwards starting from the segment, always choosing the left child if that one has a maximum of at least x, or the right one otherwise. That would be logN+logN -> O(logN) complexity for querying.

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

We can maintain a segment tree of maximum values and do it in . Suppose, we have to find next greater element for range [i + 1,  n - 1] for index i. Let us suppose the maximum of range [i + 1, n - 1] is less than a[i], then we don't have any next greater element and we return  - 1. Otherwise, check the left half and right half of the range [i + 1, n - 1]. If the maximum in left half is  ≥ a[i], you'll go to the left half in the query function of your segment tree, else you'll go the right half of your segment tree.
Now, how to implement this? Well, our range [i + 1, n - 1] actually consists of disjoint ranges in segment tree, so you'll go to the leftmost range which lies in our original range, check for the above conditions there. If it doesn't satisfies, we will return  - 1 and we don't have to go to further down the segment tree. If the leftmost range doesn't return  - 1, we don't have to go the other ranges which cover [i + 1, n - 1], so overall complexity is only.

→ Reply
»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Nice discussion of ongoing Codechef long contest problem

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Ahh. Now I understand why this was so downvoted=)))It was an almost classical problem that not everybody knows the solution for, so I thought it's a really nice blog as it gives other the chance to learn something. Couldn't the guys who downvoted say here so that I didn't comment? It's really stupid just to downvote and not hint out that you shouldn't answer the blog.

    → Reply