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.
In the ith operation, find the rightmost element in a that is smaller than k[i],
Add k[i] to the right end of a.
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)?
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])
this! i don't understand why everyone is talking about segment trees when a simple stack would do
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.
This approach is a hidden gem that I really love. Thanks for teaching me this beautiful approach!
Edit: Did I say something wrong lol?
In order to make this O(NlogN) with segment trees, do the following.
Make a SegmentTree with size equal to k.size() + a.size().
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])
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
A bit overkill, so I wouldn't recommend for this specific problem, but nonetheless a nice technique to consider!
Simple stack dude:)
Would it handle duplicates?
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 :) ).
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.
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!
Here: https://mirror.codeforces.com/problemset/problem/1450/D. Also, my observation was wrong lol.
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?
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.