Encontre a soma dos k menores elementos em uma BST (árvore binária de pesquisa)

Dada uma árvore binária de pesquisa vazia, sem quaisquer nós, você precisa executar 2 tipos de consultas:

  1. insert x – insere o valor x na BST

  2. sum k – exibe a soma dos k menores elementos na BST

Sendo q o número de consultas, você deve escrever um programa para executar essas consultas.

Entrada

A primeira linha da entrada contém um único número q (1 ≤ q ≤ 1000).

As próximas q linhas contêm as consultas. Para todas as consultas insert, o valor de x não excede em valor absoluto. Para todas as consultas sum, o valor de k não excede o tamanho atual da árvore.

Saída

Para cada consulta sum, o programa deve imprimir a soma dos k menores elementos na árvore binária de pesquisa.

Exemplos

Entrada

Saída

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

To check your solution you need to sign in
Sign in to continue