Мне нужна структура данных, в которую я хочу вставить элементы в log (n) время, и элементы должны быть отсортированы в ds после каждой вставки.Я могу использовать мультимножество для этого.
После этого я хочу найти количество элементов, строго меньшее заданного числа, снова в log (n) времени.И да, дубликаты также присутствуют, и они должны быть рассмотрены.Например, если элемент запроса равен 5, а ds содержит {2, 2, 4, 5, 6, 8, 8}, тогда ответ будет 3 (2, 2, 4), поскольку эти 3 элемента строго меньше, чем 5
Я мог бы использовать мультимножество, но даже если я использую upper_bound, мне придется использовать метод расстояния, который выполняется за линейное время.Как я могу добиться этого эффективно с C ++ STL.Также я не могу использовать