3906. [HDOJ 4006]第k大的数

【题目描述】

小明和小宝正在玩数字游戏。游戏有$n$轮，小明在每轮中都可以写一个数，或者问小宝第 $k$ 大的数是什么(第 $k$ 大的数指有$k-1$个数比它大）。

【输入格式】

输入第一行包含两个整数$n,k(1\leq k\leq n\leq 10^6)$。

接下来$n$行，每行一个操作表示一轮游戏。

I x：表示小明写下一个数$x$；

Q：表示小明询问最大的数。

输入保证当写下的数字个数小于$k$时，小明不会问小宝第$k$大的数。

【输出格式】

输入包含若干行，对于每个询问，输出一行一个整数表示第$k$大的数字。

【样例输入】

8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q

【样例输出】

1
2
3

【样例说明】

共8轮游戏，询问的时第3大的数字。

先写下3个数字：1，2，3；

询问第3大的数字，答案为1；

写下数字5，数字序列为1，2，3，5；

询问第3大的数字，答案为2；

写下数字4，数字序列为1，2，3，5，4；

询问第3大的数字，答案为3。

【数据范围与约定】

对于30%的数据，$1\leq k\leq n\leq 1000$；

对于100%的数据，$1\leq k\leq n\leq 10^6$。