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