Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

The rightmost element in an array smaller than the current element

Правка en1, от tgp07, 2022-04-13 18:36:26

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

Теги segment tree?, arrays, min

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский tgp07 2022-04-13 18:36:26 538 Initial revision (published)