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

Автор memcpy, история, 7 лет назад, По-русски

Пытаюсь решить эту задачу. Запросы типов 1 и 2 можно легко обрабатывать дерамидой. А вот 3 запрос как обрабатывать не знаю, не подскажете?

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Встаёшь в вершину, в которой лежит карта i и поднимаешься от неё до корня, и насчитываешь, сколько вершин лежит левее её (с учётом отложенных переворотов).

Или можно не возиться с отложенными переворотами, а протолкнуть их по всем вершинам на пути от корня до нашей вершины. Тогда надо будет просто считать, сколько вершин в дереве левее данной.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Получается спуск за O(n)? Или я не знаю как на неявном ключе спускаться за логарифм до нужной карты

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

      Нужно хранить ссылку на вершину дерамиды для каждой карты.В процессе изменения дерева ссылка на вершину не меняется.