Как найти количество элементов в std::set, меньших чем заданное K?

Question

[bellau]

Во время решения одной задачи возникла следующая проблема:
У нас есть множество элементов (можем добавлять и удалять)
Для заданного числа нужно найти количество элементов, которые меньше чем К.

Возможный вариант как это сделать:

int d = distance(s.begin(), s.lower_bound(k));
Однако, такой поход не оптимальный, здесь написано почему.
Если вкратце, поскольку set не обладает RandomAccessIterator, то асимптотика будет линейной.

Рассмотрим идею с деревом Фенвика:

Операцию добавления и нахождения количества мы можем делать за O(log n), однако операция удаления не реализуема.

Последняя идея - декартовое дерево:

Это именно то, что нам нужно!
Данная структура позволяет выполнять эти, и не только операции за O(log n) - отличная асимптотика.
Однако, в условии олимпиады написать такую структуры - достаточно сложное и затратное по времени занятие.

Таким образом вопрос сам по себе:
Как решить поставленную задачу используя только встроенные структуры данных.

Использование библиотек типа boost нежелательно, ведь их на олимпиаде тоже нет :)

Comments

[singlebone]

А чем тебя Фенвик не устроил? Удаление реализуется симметрично добавлению - только вместо того, чтобы делать +1 соотвествующему элементу, делаешь -1

[bellau]

singlebone: Спасибо, не знал

Answer 1

[singlebone]

Если ты пишешь в GNU C++, то там есть вот такой вот чит: opentrains.mipt.ru/zksh/files/zksh2015/lectures/mi... (смотри 1.3)

Comments

[bellau]

Его и искал, где можно еще посмотреть другие лекции ЗКШ?

Answer 2

[mamkaololosha]

Можно использовать MinHeap (фиксированного размера k, или не фиксированного).

Comments

[bellau]

По сути, решение не сильно отличается от Дерамиды по неявному ключу, нужно именно решение для std::set

Answer 3

[AtomKrieg]

std::set реализован через бинарное дерево, оно отсортировано. Через алгоритм бинарного поиска можете найти - сложность O(log(n))

Comments

[bellau]

базовые методы std::set не позволяют так делать

[AtomKrieg]

bellau: Безапелляционное заявление. Какого метода вам не хватает?

[bellau]

AtomKrieg: Извините, я могу быть не прав, в таком случае напишите код, ну или псеводкод, который позволит так делать

[singlebone]

Вы не правы. std::set не обладает RandomAccess-итераторами (проще говоря, вы не можете тыкнуться в любой элемент множества за единичку, вам нужно будет итерироваться до него за О(n)), а значит, на очередной итерации бинпоиска вам придется итерироваться от его левой/правой границы до середины, что, очевидно, займет О(n) времени.