Написал решение(6479167) на задачу "Вставка ключевых значений"(Тренировка СПбГУ B #10 Декартово дерево Light), у которого асимптотика , но, видимо, с громадной константной, ибо TL 37.

Решение заключается в следующем: будем честно хранить несуществующие элементы в виде нулей, а также запомним их позиции. Т.е. сначала у нас будет декартово дерево по неявному ключу с M нулями и set с их позициями(1, 2 ... M).

Теперь, чтобы обработать Insert(i, k), мы найдем в сете позицию самого первого нуля, начиная с i-той позиции, и, если такая позиция существует, удалим его из сета и декартова дерева. Осталось только вставить k на позицию i.

Такое решение валится тестом

131072 131072
1 1 1 ... 1 1 1

На нем у меня работает 5,5 секунды

Это у меня руки кривые, или существует более адекватное решение?