BSTでk個の最小要素の合計を求める
何もノードが存在しない空のBinary Search Tree (BST) を用意し、次の2種類のクエリを実行するよう求められています:
insert x- BSTに値xを挿入する
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