Запрос диапазона: максимальный элемент больше X и меньше Y присутствует в диапазоне индексов [l: r] в массиве A

Вам дан массив A положительных целых чисел и несколько запросов.

В каждом запросе вам даны положительные целые числа X, Y, l и r.

Для каждого запроса необходимо найти максимальный элемент в диапазоне [l : r] массива A, который больше X и меньше Y. Если такого элемента нет, выведите -1.

У меня было объяснение аналогичного вопроса, где вы должны найти максимальный элемент меньше K в диапазоне массива. Но здесь я не могу применить эту логику.

Ожидаемое время равно O(log n) или полилогарифмическому времени.


arrays algorithm logarithm range-query
person Sushil Verma    schedule 06.11.2017    source источник
comment
Какой у Вас вопрос?   -  person    schedule 06.11.2017
comment
'Ожидаемое время O(log n)' Хм, ожидаемое время чего? ...подготовки метаданных, выполнения одного запроса, выполнения всех запросов? И логарифмический относительно чего? ... к длине массива, к количеству различных чисел в массиве, то есть к сумме длины массива и количества запросов?   -  person CiaPan    schedule 06.11.2017

Ответы (2)


arrow_upward
0
arrow_downward

Вам нужна структура данных Heap. Однако я всегда отмечал временную сложность с обозначением тильды вместо большого O. Таким образом, структура данных кучи с N-элементом не будет занимать больше, чем ~ 1 + logN, сравнивается и для удаления ~ 2logN, и если вы используете большой O, то это эквивалентно O ( ЛогN).

person Luai Ghunim    schedule 06.11.2017

arrow_upward
0
arrow_downward

I had an explanation of similar question where you are to find the maximum element less than K in a range of array. But here I am not able to apply that logic.

Я не знаю твоего объяснения. Но я думаю, что вы можете опираться на это.

Предположим, вы применили эту логику и нашли, что максимальный элемент меньше Y. Пусть этот максимальный элемент равен u (-1 if no such value).

if (u > X)
{
    return u;
}
else
{
    return -1;
}
person Md. Abu Nafee Ibna Zahid    schedule 06.11.2017