The kth great number

比上一个题弱了很多啊

/******************
hdu4006
2016.3.8
265MS	27104K	1383B	C++
******************/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1000000
struct node
{
    int l,r,tot;
}num[maxn*8];
void build(int rt,int l,int r)
{
    num[rt].l=l;num[rt].r=r;
    if(l==r)
    {
        num[rt].tot=0;
        return;
    }
    int mid=(l+r)/2;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    num[rt].tot=0;
}
void update(int rt,int pos)
{
    if(num[rt].l==num[rt].r)
    {
        if(num[rt].l==pos) num[rt].tot++;
        return;
    }
    int mid=(num[rt].l+num[rt].r)/2;
    if(pos<=mid) update(rt<<1,pos);
    else update(rt<<1|1,pos);
    num[rt].tot=num[rt<<1].tot+num[rt<<1|1].tot;
}
int query(int rt,int k)
{
    if(k>num[rt<<1|1].tot)
    {
        if(num[rt].l==num[rt].r)
        {
            return num[rt].l;
        }
        query(rt<<1,k-num[rt<<1|1].tot);
    }
    else query(rt<<1|1,k);
}
int main()
{
   // freopen("cin.txt","r",stdin);
    int n,k,a;
    char st[3];
    while(~scanf("%d%d",&n,&k))
    {
        build(1,1,maxn);
        while(n--)
        {
            scanf("%s",st);
            if(st[0]=='I')
            {
                scanf("%d",&a);
                update(1,a);
            }
            else printf("%d\n",query(1,k));
        }
    }
    return 0;
}