Найти сумму k наименьших элементов в BST
Предположим, у нас есть пустое бинарное дерево поиска (BST), в котором пока нет ни одного узла. Нам нужно выполнить два типа запросов:
insert x— вставить значениеxв BST.
sum k— вывести суммуkсамых маленьких элементов в BST.
Пусть всего имеется
q запросов. Задача — написать программу, которая обработает все эти запросы.Входные данные
В первой строке входных данных содержится одно число
q (1 ≤ q ≤ 1000).В следующих
q строках записаны запросы. Для всех запросов вида insert значение x по модулю не превышает . Для всех запросов вида sum значение k не больше текущего размера дерева.Выходные данные
Для каждого запроса
sum необходимо вывести сумму k наименьших элементов в бинарном дереве поиска.Примеры
Входные данные | Выходные данные |
8
insert 2
insert 1
sum 1
sum 2
insert 10
insert 20
sum 3
sum 2 | 1
3
13
3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB