Доброго времени суток %username%.
Сегодня столкнулся с задачей, в которой решение чуть-ли не брут с помощью set'а, и релиз халявный, но не все "коту масленица".
Разглашать задачи и их решения нельзя до окончания отборов, и поэтому я ничего и не буду говорить.
Но мизерная часть задачи — надо найти количество элементов меньших либо равных данного, или же просто номер элемента в set'е, и, увы, сделать это — у меня не получилось. Надеюсь понять, что за задача не будет легко :)
У меня есть итератор на начало set'а, и итератор на элемент. Как найти расстояние от первого ко второму, быстрее чем функция distance (т.е. не за линейную сложность), и возможно ли это вообще?
P.S. Итераторы двунаправленные (стандартно в set'е), если кто не знает.
Нет, нельзя. Нужно писать свое бинарное сбалансированное дерево, где можно поддерживать размеры поддеревьев и искать расстояние между вершинами за О(высоты дерева), то есть за логарифм. Легче всего пишется декартово дерево.
А по чем Вы учили дерамиду? Где, по вашему, наиболее доступно объяснено?
А то я читал несколько раз — бесполезно.
Мне вот это больше всего понравилось
http://habrahabr.ru/post/101818/
Пожалуй это лучшее, из того что есть. Помню, после прослушивания лекции, смог на контесте в ЗШ написать эту штуку, при том что до этого не писал вообще ни одной СД, и даже не уверен, что слышал про бинарные деревья поиска. Так что спасибо Виталию Гольдштейну, за прекрасную лекцию)
Ранее всплывала подобная тема: http://codeforces.com/blog/entry/5631#comments, я там оставлял линк на обсуждение на uva: там прикладывали исходник с использование реализованного в GNU C++ RB-Tree с добавление поддержки размеров поддеревьев, но, правда, на MSVC++ понятное дело не компилируется.
Забавно сколько всего интересного есть в глубинах GNU C++. Совсем недавно e-maxx находил там бор (правда без суф. ссылок).
Не помните, где он там?
Скорее всего, имелась в виду встроенная реализация patricia tree. Если порыться в ссылках отсюда, то можно будет найти упоминание этой штуки в документации и код с примером.
Просто создатели посчитали, что для класса "множество" это не нужная операция. Поддержка же её требует дополнительных вычислений, что может негативно сказаться для обычного использования стандартного класса. Подобные вещи в stl встречаются в разных местах, например, ведь никто не мешает сделать итератор класса vector так, чтобы он оставался валидным после изменения размера массива, но никто так делать не будет, потому что это бы потребовало больше тактов, хотя в редких случаях это доставляет головной боли. (например любимое многими представление графа с "пулом" рёбер)