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

Неперсистентный merge в персистентном декартовом дереве
Автор Kostroma, 12 лет назад, По-русски

Привет, codeforces!

Может ли кто-нибудь объяснить, почему в этой задаче заходит такое решение? При обработке запросов там используется обычный merge, который не создаёт новые вершины.

И да, если это кому-то поможет мне помочь, то вот ссылка на обсуждение этой задачи в топике контеста.

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

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Все очень просто.

Когда ты делаешь персистентный сплит, все вершины, достижимые движением вправо от корня левой доли и все вершины, достижимые движением влево от корня правой доли, оказываются "свежими". Когда ты "вырезаешь" отрезок [l; r], у тебя оказываются "свежими" вершины, достижимые движением от корня как только влево, так и только вправо.

Далее следует понять, что при мердже могут меняться только вершины, достижимые движением из корня в одну сторону. А они у нас все "свежие".

→ Ответить