Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Быстрый поиск среднего элемента.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Люди!
Подскажите, как можно решить следующую проблему:
Дана последовательность целых чисел.
Поступаю запросы на нахождения среднего элемента а отрезке [l; r].
Средним элементом в последовательности 0..n - 1 называют такой элемент, который имеет позицию (n - 1) / 2 в данной упорядоченной последовательности.
Как можно быстро находить такие элементы?
Заранее спасибо!
Если я правильно понял задачу, надо всего лишь найти номера первого и последнего элементов последовательности, попадающих в отрезок [l;r]. Для этого надо воспользоваться бинарным поиском. В C++ решение уже готово: функция lower_bound вернёт первый элемент, а upper_bound - 1 - последний.
Запросы только на средний элемент? Исходная последовательность не обновляется?
to Alexey
Да, запросы только на средний элемент. Нет, последовательность не обнавляется.
to e-maxx
Эм, давайте я дам пример для пояснения:
Последовательность :
i = 0 1 2 3 4 5 6 -- индекс.
1 4 5 8 3 7 0
Например, на текущем шаге нам нужно найти средний элемент на отрезке [1; 3].
Этот элемент будет 4.
Почему? Отстортим подмассив (4, 5, 8, 3) и получим (3, 4 , 5 ,8) соответственно.
Теперь найдем этот элемент -- его индекс (n - 1) / 2. n в даном случае = 5 => i = 2, т.е. 4.
Вот.
Надеюсь, это не с идущих сейчас сборов задача? Потому что эти задачи я потом в виде контестов буду прорешивать
Надеюсь, это не с идущих сейчас сборов задача?
Какие сборы ты имеешь в виду? В Минске? Или школьников?
Потому что эти задачи я потом в виде контестов буду прорешивать
Есть ли возможность поделиться материалами? 
Эту задачу можно решать специальным деревом отрезков за O(n*log n) памяти и препроцессинга и O(log^3 n) на запрос.
Идея такая: в вершине дерева будем хранить соответствующий отрезок отсортированным. Тогда на каждый запрос надо найти разбиение запрашиваемого отрезка на не более O(log n) отрезков из дерева и найти ответ на запрос бинарным поиском (количество элементов менбших данного в отсортированном списке ищется еще одним бинарным поиском)
mastersobg
Какие сборы ты имеешь в виду? В Минске? Или школьников?
Школьников, в Малоярославце.
Есть ли возможность поделиться материалами?
У меня лично нет материалов, их выкладывают нам в виде контестов на нашем сервере Я думаю, после сборов архив с задачами и тестами где-нибудь выложат.
их выкладывают нам в виде контестов на нашем сервере
В общий доступ?
mastersobg
В общий доступ?
Неа. Ну если мне дадут материалы, я, конечно, выложу их здесь на сайте.
mastersobg
Как ни странно, выложить эти задачи нельзя. Я не знаю, по какой причине такая секретность...
ну я думаю из-за того что зеркала сборов в перми и минске пока пока идут) но это только предполодение
AlexFetisov
Там идут сборы студентов, на задачи белорусов(?), а я про сборы школьников (фактически, это был их отбор на межнар). Так что секретность непонятна - эти задачи на офиц. соревнования школьников уже не дашь, студентов - тоже (аналогично, некоторые студенты участвовали в этой школе). Всякие китайцы тоже не смогут воспользоваться этими наборами (все задачи на русском). Так что непонятно, что с этими контестами можно ещё сделать Материалы прошлого года, кстати, тоже не были выложены, а вот за предыдущие года - ещё были (см. http://neerc.ifmo.ru/school)
Кстати, поздравляю саратовских школьников с тем, что опять наши составляют половину сборной России
В Минске было несколько задач с отбора школьников. Если сейчас ещё идут зеркала, то отсюда и секретность)
Я не знаком с правилами отборов в команду России на межнар, но мне все же интересно, почему вместо участника занявшего четвертое место, в команду вошел пятый? Выходит, результаты РОИ не учитываются?
denton
а, это пожалуй всё объясняет
KADR
вроде всё учитывается. но там такие странные вещи происходят: 11-классникам предпочитают 10-классников, и далеко не только при равенстве очков. аналогичный "странный" компаратор использовался и год назад, и раньше...
вообще я был в перми, а не в минске, но вроде у нас все вечерние были со сборов школьников и еще один дневной был состряпан из них)) так что несколько - это слабо сказано))
а вот с РОИ вообще косяк) не очень ясно что твориться)
Если такую задачу нужно решать на отрезке, который задается "движущимся окном", то нужно написать только k-ю порядковую статистику с деревом отрезков)
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Быстрый поиск среднего элемента.