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

Помогите с СНМ-ом[Решена]
Автор dyussenaliyev, 13 лет назад, По-русски
Доброе время суток!
Как за О(1) выкинуть какую-то вершину из множества в СНМ-е?
Кто решил, скиньте код если можно.
Заранее спасибо!
Upd:
Итак, проблема решена. Всем спасибо!
Решение:
  • Каждую вершину i подвесить саму к себе
  • Для каждой вершины i создать фиктивную вершину i'
  • Подвесить каждую i' к i
  • Теперь, во всех операциях(union, get_set, move) использовать только фиктивные вершины
Почему нужно работать только с фиктивными вершинами?
Потому, что к ним никогда ничто не подвешивается, из-за чего нам не надо перевешивать все ссылки потомков, когда если бы делали без фиктивных вершин, надо было бы перевешивать, а это долго.
Думаю объяснил более-менее понятно.
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Можно почитать что-нибудь  на тему union-find with deletions. 
Или немного модифицировать стандартную структуру данных для СНМ (path compression and union rank):
при удалении вершины из множества, помечаем ее как removed. Затем, если какая-то вершина сказала (via findSet), что ее представителем является removed узел, перенесем ее туда и уберем флаг removed.

Подобная задача была на вчерашнем контесте Rujia Liu's Present 3 
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно поподробнее пожалуйста
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Там была вообще ещё супер задачка F: Fast Matrix Operations - задачка достойная внимания и пристального изучение в свете предстоящего АСМ-финала.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится
Сомневаюсь, что это возможно. Так-как если вершина была корнем куста , который в какой-то момент образовался, то придется для кучи вершин менять указатели.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Возможно декартово дерево по неявному ключу?
Тогда как делать get и union очевидно.
move сначала за высоту дерева найдем значения по которому стоит сплитить а потом по сплитаем
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Рекомендую почитать (а ещё лучше просмотреть и прослушать) лекцию Сергея Капелиовича "Персистентные структуры данных (Persistent Data Structures)", прочитанную им на  харьковской Зимней школе 2011.

Материал выложен на сайте школы в соответствующем разделе (http://olimp.sc170.kharkov.ua/videoday4_2011 ) - выберите "Лекция" - "Скачать".

Надеюсь, что после этого задачка станет понятной и реализуемой.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Эта задача решается обычной системой непересекающихся множеств. Достаточно просто завести n дополнительных элементов, к которым ничего не будет подвешиваться http://pastie.org/1828270
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Лучше использовать связанные списки и эвристику: сливать меньший список в больший.
Тогда добавление и удаление элемента можно делать за константу. Просто разорвать список в нужном месте и склеить потом правильно, а потом в другой список дописывать просто в конец.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что, если переносимый элемент находится в голове списка (он является представителем множества)?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну так у нас каждый элемент покрашен в определенный цвет и для цвета мы храним голову, хвост, количество и сумму элементов списка этого цвета. Поэтому никаких проблем нет. Видимо, это примерно тоже, о чем пишут выше http://codeforces.com/comments/1804#comment-34328
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А, понятно. Я просто хранил не "цвет" для каждого элемента, а номер элемента, который является головой списка для множества (тогда нужно было обновить весь список, так как голова поменялась). Ваша идея проясняет все, спасибо.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Прочитав заголовок не сразу понял что такое CHМ. Первая ссылка из гугла сказала что это Стрессовое Недержание Мочи. Первая мысль - Какой помощи ждет автор? O_х

Понял о чем речь уже после открытия темы :)
→ Ответить