BST-ում (Փնտրման Բինար ծառ) ամենափոքր k արժեքների գումար գտնել
Տրված է դատարկ Փնտրման Բինար ծառ (BST), որտեղ նախնական որևէ արժեք ներմուծված չէ։ Ձեզ խնդրում են իրականացնել երկու տեսակ հարցում.
insert x–x-ի ներդնում BST-ում
sum k– տպել BST-ում առկա ամենափոքր k արժեքների գումարը
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
q հարցում, պետք է հետևաբար կատարի վերը նշված գործողությունները։Մուտք
Մուտքի առաջին տողում տրված է
q ամբողջ թիվը (1 ≤ q ≤ 1000)։Հաջորդ
q տողերը պարունակում են հարցումները։ Բոլոր insert հարցումներում x-ի արժեքը բացարձակ արժեքով չի գերազանցում 10^9-ը։ Բոլոր sum հարցումներում k-ի արժեքը չի գերազանցում ծառում առկա տարրերի քանակը։Ելք
Յուրաքանչյուր
sum k հարցման համար ծրագիրը պետք է տպի BST-ում առկա ամենափոքր 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