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 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB