Розбір

Автор та розробник: Данііл Смельський

Пироголяндія "— це дерево, вершинами якого є пекарні, а ребрами є дороги. Тоді кожна вершина містить якесь невід'ємне число (значення вершини), а кожне ребро має один з двох станів: заблоковане чи розблоковане. Будемо вважати, що дерево має корінь у вершині $1$ .

Блоки 1-5:

Запит типу $1$ : збережемо масив що відповідає за стан кожного ребра. При виклику запиту будемо змінювати стан ребра в цьому масиві.
Запит типу $2$ : запустимо $D FS$ із вершини $p$ та відвідаємо всі вершини, які знаходяться в компоненті цієї вершини. При цьому не будемо переходити по заблокованих ребрах. Змінимо значення відвіданих вершин.
Запит типу $3$ : можна викликати спочатку запит типу $5$ до вершини $p$ , щоб дізнатись її значення після застосування запиту типу $3$ . Після цього викликаємо запит типу $6$ , щоб змінити значення кожної вершини з компоненти вершини $p$ на нуль. Замінюємо значення вершини $p$ на підраховану суму.
Запит типу $4$ : повертаємо значення вершини $p$ .
Запит типу $5$ : запустимо $D FS$ із вершини $p$ та відвідаємо всі вершини, які знаходяться в компоненті цієї вершини. При цьому не будемо переходити по заблокованих ребрах. Додамо до відповіді значення відвіданих вершин.
Запит типу $6$ : запустимо $D FS$ із вершини $p$ та відвідаємо усі вершини які знаходяться у компоненті цієї вершини. При цьому не будемо переходити по заблокованих ребрах. Змінимо значення відвіданих вершин на нуль.
Запит типу $7$ : візьмемо будь-яку вершину з ненульовим значенням. Якщо такої не існує, то очевидно, що відповідь нуль. Інакше запустимо з неї $D FS$ , що буде повертати $1$ , якщо у піддереві вершини, з якої ми виходимо, є хоча б одна ненульова вершина, та $0$ інакше. Тоді, якщо ми переходимо до наступної вершини через заблоковане ребро та $D FS$ із неї повертає $1$ , то існує пара вершин (вершина, з якої ми запустили $D FS$ на початку та певна вершина з цього піддерева) така, що шлях між ними проходить через це заблоковане ребро. Отже, до відповіді слід додати $1$ .

Блок 6:

під час ініціалізації розіб'ємо дерево на компоненти, що обмежені заблокованими ребрами, та дамо кожній компоненті свій номер. Оскільки запити типу $1$ відсутні, то множина вершин кожної компоненти змінюватися не буде. Також будемо зберігати значення кожної вершини не зовсім чесно: будемо зберігати її старе значення, а справжнє ми зможемо дізнатися, застосувавши певні операції.
Для кожної компоненти будемо зберігати певні значення:
1. integer sum "— сума значень вершин компоненти.
2. integer toAdd "— значення, яке треба додати до кожної вершини цієї компоненти, щоб воно було рівним справжньому значенню вершини.
3. integer lastVertex "— остання вершина компоненти, до якої було застосовано запит типу $3$ , або нуль, якщо до вершин цієї компоненти ще не застосовувалися запити типу $3$ .
4. clear "— булева змінна, що рівна $t r u e$ , якщо до компоненти вже застосовували запит типу $3$ або запит типу $6$ , та нуль інакше.
5. cnt "— кількість вершин у цій компоненті.
Запит типу $2$ : візьмемо номер компоненти, у якій знаходиться вершина з номером $p$ , та додамо до $t o A dd$ значення $w$ .
Запит типу $3$ : можна викликати спочатку запит типу $5$ до вершини $p$ , щоб дізнатись її значення після застосування запиту типу $3$ . Після цього викликаємо запит типу $6$ , щоб змінити значення кожної вершини з компоненти вершини $p$ на нуль. Замінюємо значення вершини $p$ на підраховану суму. Змінимо значення $l a s t V er t e x$ .
Запит типу $4$ : оскільки кожна вершина зберігає своє старе значення, то треба до цього значення додати значення параметру $t o A dd$ з її компоненти.
Запит типу $5$ : оскільки значення вершини рівне $a_{p}$ + $t o A dd (p)$ (де $t o A dd (p)$ рівне значенню параметра $t o A dd$ компоненти, у якій знаходиться вершина з номером $p$ ), тоді суму значень вершин у компоненті можна визначити за формулою $s u m$ + $c n t \times t o A dd$ .
Запит типу $6$ : розглянемо два випадки залежно від значення параметру $c l e a r$ .
1. $c l e a r = f a l se$ : зробимо всі операції чесно: пройдемося по кожній вершині, замінимо її значення на нуль. Значення $s u m$ та $t o A dd$ також замінимо на нуль, а значення $c l e a r$ на $t r u e$ .
2. $c l e a r = t r u e$ : у нас є лише одна вершина, нечесне значення якої відмінне від нуля, і це вершина з номером $l a s t V er t e x$ . Отже, можна зробити те ж саме що у випадку $c l e a r = f a l se$ , але замінити лише значення вершини з номером $l a s t V er t e x$ .

Блок 7:

щоб розв'язати цей блок, можна модифікувати розв'язок до попереднього блоку. З'являється лише проблема із тим, що кількість та склад компонент можуть змінюватись.
Додамо до компонент два параметри:
1. $a ll V er t e x es$ "— вектор, що зберігає множину вершин, що знаходяться в цій компоненті.
2. $a c t i v e V er t e x es$ "— вектор, що зберігає множину вершин, що знаходяться в цій компоненті та мають нечесне значення відмінне від нуля.
Через запит типу $1$ треба вміти поєднувати певні компоненти. Для цього застосуємо структуру даних $D i s j o in tS e t U ni o n$ (система неперетинних множин).
Розглянемо операцію $u ni o n S e t s$ , застосовану до компонент із номерами $x$ та $y$ у нашій $D S U$ . Вона повинна поєднати дві компоненти. Будемо вважати, що це лідери відповідних компонент у $D S U$ та вони різні. Ми будемо підвішувати компоненту з номером $y$ до компоненти з номером $x$ . Тоді нам треба якось поєднати їх параметри. Для цього спочатку очистимо список $a c t i v e V er t e x es (y)$ , а потім пройдемося по вершинах компоненти $y$ (список $a ll V er t e x es (y)$ ), якщо значення $c l e a r = t r u e$ , тоді спочатку замінимо значення вершини на нуль, а потім замінимо значення кожної з них на $a_{p} = a_{p} + t o A dd (y) - t o A dd (x)$ , додамо кожну з них до списку $a c t i v e V er t e x es (y)$ , а до $s u m (y)$ додамо $c n t (y) \times t o A dd (y)$ . Далі перекинемо вершини зі списку $a ll V er t e x es (y)$ до списку $a ll V er t e x es (x)$ , а також вершини зі списку $a c t i v e V er t e x es (y)$ до списку $a c t i v e V er t e x es (x)$ . Додамо до $s u m (x)$ значення $s u m (y)$ , а до $c n t (x)$ значення $c n t (y)$ . Підвісимо вершину $y$ до вершини $x$ у $D S U$ .
Які зміни відбулися у запитах?
- Запит типу $2$ : змін немає, лише треба брати номер компоненти з $D S U$ .
- Запит типу $3$ : після виклику запиту типу $6$ наш список $a c t i v e V er t e x es$ повинен містити лише вершини $p$ , але він є порожнім, тому треба додати до нього вершину з номером $p$ , якщо її значення після цього запиту є ненульовим.
- Запити типу $4$ та $5$ : відповіді можна знайти так само як у блоці $6$ .
- Запит типу $6$ : у розв'язку до шостого блоку ми фактично проходилися по списку $a ll V er t e x es$ , але помітимо, що можна проходитись лише по списку $a c t i v e V er t e x es$ та замінювати лише їх значення на нуль. Після цього слід видалити всі вершини зі списку $a c t i v e V er t e x es$ .
Асимптотика такого розв'язку не буде вкладатися в обмеження, бо може перевищувати $O (n^{2})$ . Проте можна застосувати техніку $s ma ll$ - $t o$ - $l a r g e$ (від меншого до більшого). Перш ніж оброблювати запит типу $1$ , давайте упорядкуємо $x$ та $y$ так, щоб $c n t (x)$ було не меншим за $c n t (y)$ . Тоді асимптотика такого рішення вже буде $O (n lo g n)$ , що повинно проходити цей блок.

Блок 8:

оскільки компоненти не будуть змінюватись у складі, можна побудувати додаткове дерево. Для цього давайте умовно видалимо з нашого дерева всі заблоковані ребра та стиснемо кожну компоненту, що утворилася в одну вершину в новому дереві. Усі нові вершини ми якось пронумеруємо, а також для кожної вершини початкового дерева запам'ятаємо номер вершини, до якої вона увійшла в новому дереві. Тепер додамо до цього дерева заблоковані ребра, що ми видалили на початку його побудови. Підвісимо це дерево за будь-яку вершину. Будемо вважати, що вершина в новому дереві має чорний колір, якщо є хоча б одна вершина з ненульовим значенням у початковому дереві, що належить цій вершині в новому дереві. Переформулюємо запит сьомого типу: треба знайти мінімальну кількість ребер у новому дереві, які потрібно розблокувати, щоб на шляху між кожною парою чорних вершин усі ребра були розблоковані.
Розглянемо будь-яке ребро з нового дерева. За якої умови його треба розблокувати? Якщо у піддереві нижньої вершини (більш віддаленої від кореня) цього ребра є хоча б одна вершина чорного кольору та ззовні піддерева верхньої вершини є хоча б одна вершина чорного кольору, то це ребро треба розблокувати. Інакше не існує пари вершин чорного кольору, на шляху між якими лежить це ребро, отже, його розблоковувати не потрібно.
Запустимо $D FS$ з кореня нового дерева та випишемо вершини чорного кольору у порядку часу входження до них. Нехай це послідовність $g$ довжини $k$ . Уведемо нову функцію $d i s t (x, y)$ "— кількість ребер на шляху між парою вершин $x$ та $y$ у новому дереві. Звідси отримуємо формулу для визначення відповіді на запит сьомого типу: $an s = (d i s t (g_{1}, g_{2}) + d i s t (g_{2}, g_{3}) + \dots + d i s t (g_{k - 1}, g_{k}) + d i s t (g_{k}, g_{1}))$ / $2$ . Чому це правильно? Знову розглянемо будь-яке ребро з нового дерева. Якщо існує вершина чорного кольору у піддереві нижньої вершини цього ребра та вершина чорного кольору ззовні верхньої вершини цього ребра, то це ребро увійде до суми рівно два рази, бо воно увійде в це піддерево та вийде з нього. Інакше воно жодного разу не увійде до цієї суми.
Отже, для розв'язання сьомого типу запитів треба вміти підтримувати цю суму. Оскільки відсутні запити першого типу, склад нового дерева змінюватися не буде, але вершини можуть змінювати колір. Давайте зберігати таку суму: $q u er y_{7} = d i s t (g_{1}, g_{2}) + d i s t (g_{2}, g_{3}) + \dots + d i s t (g_{k - 1}, g_{k})$ Тоді нас цікавлять лише зміни, що відбуваються у послідовності $g$ . У нас може або додаватися новий елемент до послідовності, можливо, десь у середину, або видалятися.
Випишемо в окремий масив усі вершини нового дерева у порядку часу входження до них при виклику $D FS$ з кореня. Тобто коли $D FS$ входить у нову вершину, поточний час збільшується на $1$ . Звідси $t in (v)$ "— час входження до вершини $v$ , а $t o u t (v)$ "— час виходу з вершини $v$ . Особливість цього порядку в тому, що всі вершини з піддерева вершини $v$ зустрічаються на відрізку $t in (v) \dots t o u t (v)$ у цій послідовності. Для кожної вершини запам'ятаємо позицію, на якій вона зустрічається у цьому масиві. Якщо вершина має чорний колір, то в додатковому масиві на її позицію поставимо одиничку, інакше нуль. Як треба оброблювати зміни у новому дереві?
- Зміна кольору вершини з чорного на білий. Припустимо, що ця вершина зустрічалась на позиції $u$ в послідовності $g$ . Тоді у формулу для знаходження значення $q u er y_{7}$ вона могла увійти максимум у двох доданках.
  1. $u > 1$ : $d i s t (g_{u - 1}, g_{u})$
  2. $u < k$ : $d i s t (g_{u}, g_{u + 1})$
  Тоді нам треба перевірити можливі випадки та вміти знаходити відстань між двома вершинами, а потім віднімати їх від суми. Для цього можна скористатися додатковими структурами даних.
- Зміна кольору вершини з білого на чорний аналогічна, але тепер треба додавати числа до нашої суми.
щоб дізнатися відповідь на запит сьомого типу, до нашої суми треба додати значення $d i s t (g_{1}, g_{k})$ , а потім поділити суму на два. Щоб знайти першу та останню чорну вершини, звернемося до нашого масиву з нуликів та одиничок. Можемо на цьому масиві побудувати дерево відрізків та швидко знаходити наші вершини (можна зробити $se t$ , але дерево відрізків нам знадобиться для вирішення наступних блоків).

Блок 9:

Випишемо всі вершини нашого дерева у порядку часу входження в них у $D FS$ , викликаного з кореня дерева. Тепер для кожної вершини у додатковому масиві, на позиціях де вони зустрічаються у масиві часу входження, будемо зберігати кількість заблокованих ребер на шляху від кореня до цієї вершини. Тоді всі вершини з піддерева вершини $v$ , що ще й знаходяться в компоненті вершини $v$ , мають те ж саме значення у додатковому масиві, що й значення вершини $v$ . Згадаємо, що вершини піддерева вершини $v$ знаходяться на відрізку $t in (v) \dots t o u t (v)$ у масиві обходу $D FS$ . Важливий факт, який треба помітити, "— значення вершини $v$ на цьому відрізку в додатковому масиві мінімальне. А отже, усі вершини, що мають мінімальне значення на цьому відрізку, знаходяться в компоненті вершини $v$ . Тобто якщо визначити в кожній компоненті її корінь (найближчу вершину до кореня всього дерева), тоді ця компонента може бути визначена як множина вершин, що лежать на відрізку $t in (v) \dots t o u t (v)$ , та мають на ньому мінімальне значення.
Побудуємо на додатковому масиві дерево відрізків. Кожен лист цього дерева буде відповідати за певну вершинку початкового дерева, визначену за номером вершини у масиві обходу $D FS$ . У кожному листі дерева відрізків будемо зберігати пару параметрів:
1. значення вершини
2. значення вершини у додатковому масиві (кількість заблокованих ребер на шляху від кореня дерева до цієї вершини)
А для інших вершинок дерева відрізків, що відповідають за певні проміжки, будемо зберігати наступні параметри:
1. сума значень усіх вершин з цього проміжку
2. мінімальне значення у додатковому масиві усіх вершин з цього проміжку
3. кількість вершин із мінімальним значенням на цьому проміжку
4. додаткові параметри, які умовно будемо називати обіцянками, щоб оброблювати певні операції на цьому дереві.
Перейдемо до розв'язку запитів:
- Запити типу $1$ : подивимося на піддерево нижньої вершини цього ребра. Оскільки це ребро заблоковане, то воно додає $1$ до значення кожної вершини у додатковому масиві з цього проміжку. Тобто у дереві відрізків треба відняти $1$ від додаткового значення кожної вершини з цього проміжку, а це можна зробити використовуючи обіцянку $a dd 1$ "— число, на яке треба змінити додаткове значення кожної вершини з цього проміжку.
- Запити типу $2$ : спочатку знайдемо корінь компоненти, у якій знаходиться ця вершина (як це зробити, дивіться після розв'язку блоку $9$ ). Нехай це вершина $v$ . Тоді до значення всіх вершин з компоненти вершини $v$ треба додати число $w$ . Оскільки ці вершини знаходяться на відрізку $t in (v) \dots t o u t (v)$ та мають мінімальне значення на ньому, то можна використати наше дерево відрізків, а саме ще один параметр для обіцянок $a dd 2$ "— число, на яке треба змінити значення кожної вершини з цього проміжку.
- Запити типу $3$ : викличемо запит типу $5$ та $6$ . Запит типу $6$ лише замінив значення кожної вершини нашої компоненти на нуль, але значення додаткового параметру не змінилось. Отже, ми можемо додати до значення нашої вершини $p$ суму, підраховану в запиті типу $5$ , використавши наше дерево відрізків для проміжку $t in (p) \dots t in (p)$ .
- Запити типу $4$ : використовуючи обіцянки, ми можемо дізнатися значення окремої вершинки, поступово спускаючись до неї по дереву відрізків та перекидаючи обіцянки до синів поточної вершини.
- Запити типу $5$ : щоб дізнатися відповідь на цей запит, треба взяти суму значень усіх мінімумів на відрізку $t in (v) \dots t o u t (v)$ , де $v$ "— корінь компоненти вершини $p$ . Наше дерево відрізків уже зберігає цю суму для часткових проміжків, тому треба обрати головні з них та комбінувати.
- Запити типу $6$ : будемо використовувати ще один параметр обіцянки в дереві відрізків $c l e a r$ "— чи було очищення кожної вершинки із мінімальним значенням на проміжку цієї вершинки дерева відрізків.
- Слід зауважити, що на відміну від перекидування обіцянок у звичайному дереві відрізків (наприклад, звичайне додавання на відрізку), у цьому дереві відрізків ми будемо передавати обіцянку лише до синів із мінімальним значенням. Це стосується всіх обіцянок, окрім $a dd 1$ , яку слід передавати так само, як у звичайному дереві відрізків.
- Отже, асимптотика такого рішення буде $O (n lo g n)$ .

Як ефективно знаходити корінь кожної компоненти (із можливістю застосовувати запити першого типу):

знову випишемо всі вершинки у порядку обходу $D FS$ , а також повернемося до параметрів $t in (v)$ та $t o u t (v)$ . Заблокованими будемо називати ті вершинки, ребро з яких до предка у дереві заблоковане. Отже, зробимо ще один додатковий масив. Якщо вершина заблокована, або це вершинка $1$ (корінь дерева), то на її позиції будемо зберігати значення $t o u t (v)$ , а інакше будемо на її позиції зберігати нуль.
Як знаходити корінь компоненти: по-перше, усі предки нашої вершини будуть знаходитись на позиціях із номерами, меншими ніж $t in (p)$ , тобто на відрізку $1 \dots t in (p)$ . А також, за властивістю $t in$ та $t o u t$ , значення $t o u t (v)$ повинно бути більшим або рівним за $t o u t (p)$ , якщо $v$ предок $p$ . Якщо є дві вершини, що є кандидатами на корінь нашої компоненти, то серед них треба обрати останню. Тобто лідер компоненти вершини $p$ це остання вершинка на відрізку $1 \dots t in (p)$ , на позиції якої стоїть значення, що не менше за $t o u t (p)$ .

Блок 11:

Єдине, що ми ще не розглянули, це як одночасно підтримувати запити першого та сьомого типу. Тепер у нас може змінюватися структура нашого нового дерева, що було побудоване на стиснутих компонентах, тому будувати нове дерево може виявитися занадто незручно. Зробимо копію нашого початкового дерева. І тепер чорними будуть вершини, що є коренями компонент, що містять хоча б одну вершину з ненульовим значенням. Тоді змінилась функція $d i s t (x, y)$ "— кількість заблокованих ребер на шляху між вершинами $x$ та $y$ . Проте ми можемо дізнатися її значення, використовуючи значення наших додаткових параметрів у дереві відрізків, що ми застосовували для вирішення перших $6$ типів запитів.
Тепер при виклику запиту типу $1$ треба вміти поєднувати дві компоненти та ділити одну компоненту на дві. Це ми можемо зробити певною послідовністю фарбувань вершин з білого кольору на чорний та навпаки, залежно від складу компонент.
Проте нам треба зауважити, що це ребро могло входити до значення $q u er y_{7}$ . Давайте спочатку змінимо його стан, перерахувавши значення $q u er y_{7}$ , а потім будемо поєднувати або ділити компоненти.
1. Зміна стану ребра з розблокованого до заблокованого: треба дізнатися, скільки разів це ребро буде входити до суми. Згадаємо про масив, де ми зберігаємо $1$ на позиціях чорних вершин та $0$ на позиціях білих. Тоді, якщо на відрізку $t in (p) \dots t o u t (p)$ зустрічається хоча б одна одиничка та на відрізку $1 \dots t in (p) - 1$ також зустрічається хоча б одна одиничка, тоді існує доданок $d i s t (q, p)$ , що має входити до значення $q u er y_{7}$ . Тобто до цього значення слід додати $1$ . Так само якщо на відрізку $t in (p) \dots t o u t (p)$ трапляється хоча б одна одиничка та на відрізку $t o u t (p) + 1 \dots n$ також трапляється хоча б одна одиничка, то є доданок $d i s t (p, q)$ , що має входити до значення $q u er y_{7}$ , тобто це значення треба знову збільшити на $1$ .
2. Зміна стану ребра із заблокованого на розблоковане: аналогічно до першого випадку, проте треба віднімати $1$ від значення $q u er y_{7}$ .
Асимптотика рішення $O (n lo g n)$ .