Дерево#4325
Розглянемо кореневе дерево. Спочатку дерево складається лише з одного кореня. Для синів кожної вершини визначено порядок зліва направо. Допустимі операції з деревом такі:
Додати у дерево лист.
Видалити з дерева лист.
Знайти кількість вершин на шляху між двома листками.
Знайти кількість "під шляхом" між двома листками.
Множина вершин, яка лежить "під шляхом" між листками та , визначається наступним чином. Розглянемо шлях u = w_0 - w_1 - \ldots - w_k = v між ними. Виділимо у ньому ту вершину w_c, у якій обидва ребра шляху йдуть до її синів. Нехай для визначенності ліве з цих ребер наближає нас до вершини , а праве — до вершини . Тоді такими, що лежать "під шляхом", оголошуються наступні вершини:
Усі сини w_c, які лежать між w_{c-1} та w_{c+1}, а також усі вершини їхніх піддерев;
Для i = 1, 2, \ldots, c-1 — усі сини w_i, які лежать правіше сина w_{i-1}, а також усі вершини їхніх піддерев;
Для i = c+1, c+2, \ldots, k-1 — усі сини w_i, які лежать лівіше сина w_{i+1}, а також усі вершини їхніх піддерев.
Напишіть програму, яка за послідовністю запитів перебудовує дерево згідно з запитами на додавання та видалення вершин, а також обчислює відповіді на запити про кількість вершин на шляху і "під шляхом".
У першому рядку вхідного файлу міститься одне ціле число — кількість запитів (0 \leq n \leq 300\,000). Кожен з наступних рядків описує один запит. Можливі види запитів такі:
l x — додати новий лист як самого лівого сина вершини .
r x — додати новий лист як самого правого сина вершини .
a x y — додати новий лист як сина вершини , який знаходиться безпосередньо праворуч від вершини ; усі сини , які знаходилися до цього праворуч від , після додавання опиняються правіше нової вершини; гарантується, що є сином .
d x — видалити вершину . Гарантується, що у цей момент вершина не видалена і є листком.
p x y — знайти кількість вершин на шляху між та , включаючи самі ці вершини; гарантується, що та є листками.
q x y — знайти кількість вершин "під шляхом" між та , включаючи самі ці вершини; гарантується, що та є листками.
Вершини, що додаються, нумеруються з одиниці у тому порядку, у якому вони додаються у запитах. Корінь дерева має номер і листком ні в який момент часу не вважається.
Виконуючи запити по порядку, на кожен запит виду p або q виведіть відповідь на нього у окремому рядку.
Приклад 1