Задача №113269. Дерево
Рассмотрим корневое дерево. Изначально дерево состоит из одного лишь корня. На сыновьях каждой вершины определён порядок слева направо. Допустимые операции с деревом таковы:
- Добавить в дерево лист.
- Удалить из дерева лист.
- Найти количество вершин на пути между двумя листьями.
- Найти количество вершин "под путём" между двумя листьями.
Множество вершин, лежащих "под путём" между листьями \(u\) и \(v\), определяется следующим образом. Рассмотрим путь \(u = w_0\) - \(w_1\) - \(\ldots\) - \(w_k = v\) между ними. Выделим в нём ту вершину \(w_c\), в которой оба ребра пути идут в её сыновей. Пусть для определённости левое из этих рёбер приближает нас к вершине \(u\), а правое - к вершине \(v\). Тогда лежащими "под путём" объявляются следующие вершины:
- Все сыновья \(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}\), а также все вершины их поддеревьев.
Напишите программу, которая по последовательности запросов перестраивает дерево согласно запросам на добавление и удаление вершин, а также вычисляет ответы на запросы о количестве вершин на пути и "под путём".
В первой строке ввода содержится одно целое число \(n\) - количество запросов (\(0 \le n \le 300\,000\)). Каждая из следующих \(n\) строк описывает один запрос. Возможные виды запросов таковы:
| l \(x\) | добавить новый лист как самого левого сына вершины \(x\) |
| r \(x\) | добавить новый лист как самого правого сына вершины \(x\) |
| a \(x\) \(y\) | добавить новый лист как сына вершины \(x\), находящегося непосредственно справа от вершины \(y\); все сыновья \(x\), находившиеся до этого справа от \(y\), после добавления оказываются правее новой вершины; гарантируется, что \(y\) является сыном \(x\) |
| d \(x\) | удалить вершину \(x\); гарантируется, что в этот момент вершина \(x\) не удалена и является листом |
| p \(x\) \(y\) | найти количество вершин на пути между \(x\) и \(y\), включая сами эти вершины; гарантируется, что \(x\) и \(y\) являются листьями |
| q \(x\) \(y\) | найти количество вершин <<под путём>> между \(x\) и \(y\), включая сами эти вершины; гарантируется, что \(x\) и \(y\) являются листьями |
Добавляемые вершины нумеруются с единицы в том порядке, в котором они добавляются в запросах. Корень дерева имеет номер \(0\) и листом ни в какой момент времени не считается.
10 l 0 r 0 l 1 r 2 a 0 1 r 4 p 6 5 l 2 q 3 6 d 7
5 2