BSTでk個の最小要素の合計を求める

何もノードが存在しない空のBinary Search Tree (BST) を用意し、次の2種類のクエリを実行するよう求められています:

  1. insert x - BSTに値xを挿入する

  2. sum k - BSTの中から最も小さい要素k個の合計を出力する

クエリがq個与えられるので、これらのクエリを処理するプログラムを書いてください。

入力

最初の行には、整数q (1 ≤ q ≤ 1000) が与えられます。

続くq行にはクエリが与えられます。すべてのinsertクエリで挿入されるxの絶対値はを超えません。また、sum kクエリのkは、常に現在のBSTのサイズ以下になります。

出力

sum kクエリに対して、BSTの中で最も小さい要素k個の合計を1行に出力してください。

入力

出力

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