Nurlan Zhusupov


Задача №1. 

Задача F. Обещаю, последняя задача с деревом :)

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

Дано подвешенное бинарное дерево изначально состоящее из одной вершины с номером 1. Вам предстоит обработать $M$ запросов следующих типов : Получится ли у Вас решить эту задачу?
Формат входного файла
Первая строка входного файла содержит целое число $M$ $(1 \leq M \leq 2 \cdot 10^5)$ — количество запросов. В последующих $M$ строках содержится описания операций. Каждая операция описывается строкой $Op$ $V$, где $Op$ — тип операции ($Grow$ либо $Sum$), а $V$ — номер вершины для которой она выполняется.
Формат выходного файла
Для каждой операции типа $Sum$ в выходной файл на отдельной строке необходимо вывести соответствующую сумму. Выводите операции в том же порядке в котором они идут во входном файле.
Система оценки
Данная задача содержит семь подзадач:
  1. $1 \leq M \leq 20$. Оценивается в $15$ баллов.
  2. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Grow$ $V$. Оценивается в $10$ баллов.
  3. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Sum$ $V$. Оценивается в $10$ баллов.
  4. $1 \leq M \leq 10^3$. Оценивается в $15$ баллов.
  5. $1 \leq M \leq 2 \cdot 10^5$, гарантируется что все запросы $Sum$ идут строго после всех запросов $Grow$. Оценивается в $15$ баллов.
  6. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^6$. Оценивается в $15$ баллов.
  7. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^9$. Оценивается в $20$ баллов.
Пример:
Вход
5
Grow 1
Grow 1
Grow 2
Sum 1
Sum 4
Ответ
66
21
( Nurlan Zhusupov )
комментарий/решение олимпиада