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)?
