Республиканская олимпиада по информатике 2017 год, Павлодар

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Дано подвешенное бинарное дерево изначально состоящее из одной вершины с номером 1. Вам предстоит обработать $M$ запросов следующих типов :

• $Grow$ $V$. К каждому листу $leaf$ в поддереве вершины $V$ дописать две новые вершины с номерами $2 \cdot leaf$ и $2 \cdot leaf+1$.
• $Sum$ $V,$ нужно подсчитать сумму номеров вершин в поддерево вершины $V$ по модулю $10^9+7$.

Получится ли у Вас решить эту задачу?

Формат входного файла

Первая строка входного файла содержит целое число $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 )