AT_abc212_d [ABC212D] Querying Multiset
题目描述
高桥君有许多还没有写字的球和一个袋子。最开始袋子是空的,高桥君将依次进行 q 次操作。每次操作是以下三种之一:
∙操作 1:在一个还没有写字的球上写下整数 x,然后把它放进袋子;
∙操作 2:将袋子里所有球上写的数都加上 x;
∙操作 3:从袋子里取出写有最小数字的球(如果有多个,任选一个),记录下这个数字,然后把这个球丢弃。
给定每次操作的类型,以及操作 1、操作 2 中的 x,请你按照顺序输出每次操作 3 记录下的数字。
输入格式
第一行输入一个整数 q(1≦q≦2×105) 代表操作次数。
此后 q 行,第 i 行输入第 i 个操作,每行先输入一个整数 pi(1≦pi≦3) 代表操作类型,编号同题干:
∙若 pi=1,紧接着在同一行输入一个整数 xi(1≦xi≦109) 代表写在新球上的数;
∙若 pi=2,紧接着在同一行输入一个整数 xi(1≦xi≦109) 代表给袋中所有球加上的数;
∙若 pi=3,该行只有 pi 一个整数。
保证至少存在一次操作 3,并且每次操作 3 执行前,袋子里至少有一个球。
输出格式
对于每一次操作 3,新起一行输出当时记录下的数字。注意,答案可能超出 32 位整数的范围。
测试样例
5
1 3
1 5
3
2 2
3
3
7
样例 1 解释
高桥君依次进行如下操作:
∙操作 1(x1=3):把写有 3 的球放入袋子,袋中球的数字为 {3};
∙操作 1(x2=5):把写有 5 的球放入袋子,袋中球的数字为 {3,5};
∙操作 3:取出写有最小数字的球,记录 3,然后丢弃,袋中球的数字为 {5};
∙操作 2(x4=2):袋中所有球的数字都加上 2,变为 {7};
∙操作 3:取出写有最小数字的球,记录 7,然后丢弃,袋子变为空。
因此依次输出 3 和 7。
6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3
5000000000