Nearest greater element

Правка en1, от sas, 2017-10-09 07:38:28

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

Теги #data structure, #rmq

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский sas 2017-10-09 07:38:28 366 Initial revision (published)