[SDOI2007]超级数组

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 arr.in 输出文件 arr.out

Source: SDOI2007 Day2
【问题描述】

一般的数组大家都经常使用,相信很多同学没有见过下面的超级数组。
超级数组存储的是一些正整数,它还支持下面的两个操作
(1)、插入一个元素,命令是 "i key" 。 key 是要插入的数。
(2)、输出第 k 大元素并删除该元素,命令是 "d k"。输出第 k 大元素并删除它。
“第 k 大”是指:现有的数中,如果从小到大排好序,从最小的开始作为第一大算起,
一直数到第 k 个。
现在给出一个开始是空的超级数组,请维护好该数组。
【输入】(arr.in)
第一行 n、m:n<=1 000 000 000 , m<=100 000。表示插入数的范围是 1 至n ,共有m 条
命令(包括插入和删除)。
以下 m 行,每行一条命令,如题中描述。每条命令中字母和后面的数字之间一个空格。
保证输入数据是正确的,删除的数一定存在。
【输出】(arr.out)
对于每个删除命令,按删除命令顺序输出删除的数,每个数一行
【样例输入】
100 10
i 57
i 99
i 65
d 3
i 89
d 2
d 2
d 1
i 93
i 29
【样例输出】
99
65
89
57