Сегодня решали один контест и все бы хорошо, но столкнулись с проблемой — задача, которая работает за N log N при N <= 200000, должна была залетать с плюса, но не тут-то было. http://pastebin.com/FSTU1yYQ хорошо видно, что программа действительно работает за N log N : N раз добавляем в set элементы, и столько же раз используем upper_bound. У нас возник вопрос, почему же мы получили TL? Решили разобраться и кроме как спихнуть все на iterator.operator--() и ++() мы ничего не придумали. Может кто объяснит, почему так получается??

P.S. написали эту же задачу на дереве отрезков — все зашло... Так что решение верное.