Во время решения одной задачи возникла следующая проблема:
У нас есть множество элементов (можем добавлять и удалять)
Для заданного числа нужно найти количество элементов, которые меньше чем К.
Возможный вариант как это сделать:
int d = distance(s.begin(), s.lower_bound(k));
Однако, такой поход не оптимальный, здесь написано почему.
Если вкратце, поскольку set не обладает RandomAccessIterator, то асимптотика будет линейной.
Рассмотрим идею с деревом Фенвика:
Операцию добавления и нахождения количества мы можем делать за O(log n), однако операция удаления не реализуема.
Последняя идея - декартовое дерево:
Это именно то, что нам нужно!
Данная структура позволяет выполнять эти, и не только операции за O(log n) - отличная асимптотика.
Однако, в условии олимпиады написать такую структуры - достаточно сложное и затратное по времени занятие.
Таким образом вопрос сам по себе:
Как решить поставленную задачу используя только встроенные структуры данных.
Использование библиотек типа boost нежелательно, ведь их на олимпиаде тоже нет :)
