tgp07's blog

The rightmost element in an array smaller than the current element
By tgp07, history, 2 years ago, In English

I was working on a problem, and I managed to reduce it to the following question:

Given two arrays of integers a[0], and k[n], perform the following operation n times.

  1. In the ith operation, find the rightmost element in a that is smaller than k[i],

  2. Add k[i] to the right end of a.

  3. Do 1 & 2 n times

I'm trying to use Segment Trees on this, but I'm not able to get the right construction.

Does anyone have a way to do this efficiently(under n^2)?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

If an element is larger than another element and also precedes it we can ignore it, so you can maintain a list of decreasing elements from right to left (Think about it like a stack, but implementation-wise it will probably be better as a vector / deque because of the next step), then perform a binary search on it (pick the biggest that is smaller than K[i])

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

    this! i don't understand why everyone is talking about segment trees when a simple stack would do

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

You can do coordinate compression on all elements in K, then you make a segment tree on array B, where B[x] = latest occurrence of x in array A. So now finding rightmost element in A that is smaller than K[i] becomes a maximum query on range [0; K[i]-1]. After query, update B[K[i]] = i.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This approach is a hidden gem that I really love. Thanks for teaching me this beautiful approach!

    Edit: Did I say something wrong lol?

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

In order to make this O(NlogN) with segment trees, do the following.

  1. Make a SegmentTree with size equal to k.size() + a.size().

  2. At the start, push all elements from A there, and then, when you have to add k[i], call point update on pos = a.size() + i (so make a[a.startSize + i] = k[i])

  3. Then, do the following:

Call recursively from Node V(at the start, this is the node responsible for the whole segment): Consider its two sons

If the right son is v.r and left son is v.l, you can do the following:

if v.r min < k[i], then there exists an element there less than k[i], and you need to only consider that segment (call recursively from v.r) otherwise, call from v.l, as that's where the minimum is

This technique is called descending the Segment Tree

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

    A bit overkill, so I wouldn't recommend for this specific problem, but nonetheless a nice technique to consider!

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple stack dude:)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would it handle duplicates?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you need to add a number to the stack only if it is strictly smaller than the top one ( you can look at my comment if you don't understand :) ).

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Next time, can you post where you got the problem statement from? I know it can be a pain, but it ensures that we are not abetting in cheating from some ongoing contest.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, didn't know codeforces is used (Not in this post I assume) to cheat in other websites, thanks for letting me know, will be more careful next time!

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Here: https://codeforces.com/problemset/problem/1450/D. Also, my observation was wrong lol.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you prove that this problem isn't binary searchable? Like if you can make a permutation with the first K, you can also make one with the first K + 1?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Actually, the observation helped a lot lol. I got it AC using segment tree and prefix sums.

        Also, I'm not sure your observation is correct(I thought so too). Look at one of the example tc's: 1011. Is this binary searchable?

        My submission: 153769266.

        I used EnDeRBeaT's approach because that was honestly the easiest to understand lol.

        → Reply