Блог пользователя Ancient_mage

Set::iterator, set::lower_bound().
Автор Ancient_mage, 10 лет назад, По-русски

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

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

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится 
set<int> s;
lower_bound(s.begin(), s.end(), x); // O(n) или O(n log n), не уверен. Не логарифм, это точно
s.lower_bound(x); // O(log n)
→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Логарифм в квадрате. В первом случае запускается бинпоиск по элементам множества.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Нет, у сета нет произвольного доступа (random access), поэтому запускается линейный поиск.

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

upper_bound() и lower_bound() надо вызывать как методы сета, т.е. SET.lower_bound(val);

→ Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо) Понял одну строчку — получил AC. Я так понял, когда вызываем не как метод класса, то оно как-то по-другому работает. Не могли бы вы объяснить, почему так разница в асимптотике?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

    Потому что иначе там вызывается стандартный бинарный поиск, на каждом шаге которого вычисляется срединный итератор. Он считается как leftIterator() + len / 2 и вот это прибавление делается по единичке, т.к. сетовые итераторы (в отличие от вектора, например) не умеют мгновенно инкрементнуться на произвольное значение.

    Если же вызвать метод сета, то он, зная реализацию сета, может ее использовать, в частности он может найти нужный элемент одиночным спуском по дереву.

    → Ответить