Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » 1439 timus
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Как решить эту задачу - http://acm.timus.ru/problem.aspx?space=1&num=1439 за Nlog(N)?; очевидная идея - к-тая порядковая статистика за log(N)*log(N) сумматором или log(N) каким-нибудь сбалансированным деревом не катит из-за ограничения на N = 10^9 - массив такой длины не объявить (. Пытался приспособить сжатие координат, но что-то контрпримеры находятся(.
Я решал с помощью treap + binary search. Зачем массив на N для сбалансированного дерева ?
Для сбалансированного дерева нужен не массив на N, а set<int> на N. Если там хранить неудаленные числа - то, есть в начале все числа от 1 до N, то как раз запрос сводится к нахождению к-того элемента в сете (то есть сет придется писать ручками). Я не знаком с treap, но это же дерево, разве его не надо хранить в виде массива на N по аналогии с деревом отрезков? или там структура из указателей?
Про treap есть отличная статья здесь http://e-maxx.ru/algo/treap 
Ну а вообще суть решения в том, чтобы хранить все неудаленные числа в виде набора непересекающихся отрезков(тогда каждый запрос на удаление числа увеличит количество отрезков не более чем на 1).
А я в дереве хранил настоящие позиции удаленных комнат, с этой информацией тоже можно отвечать на запросы.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » 1439 timus