HDU 2852 Kiki 's K - Number (가중치 선분 트 리 가 k 번 째 로 크다)

  ：    ，0 e         e，1 e         e，2 e k      e   k  ，          
  。

  ：        ，              。    ，   1 e     n，     k+n 。

#include
#include
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 1e5 + 10;
const int N = 100000;
int num[maxn<<2];
void update(int pos,int val,int l,int r,int rt)
{
    if(l==r)
    {
        if(num[rt]+val<0)
        {
            printf("No Elment!
");
            return ;
        }
        num[rt] += val;
        return ;
    }

    int m = l + r >> 1;
    if(pos<=m)
        update(pos,val,lson);
    else
        update(pos,val,rson);
    num[rt] = num[rt<<1] + num[rt<<1|1];
}

int query(int k,int l,int r,int rt)//  k 
{
    if(num[rt]printf("Not Find!
");
        return -1;
    }
    if(l==r)
        return l;
    int m = l + r >> 1;
    if(k<=num[rt<<1])
        return query(k,lson);
    else
        return query(k-num[rt<<1],rson);
}

int query(int L,int R,int l,int r,int rt)//L<= <=R     
{
    if(L<=l&&r<=R)
        return num[rt];
    int m = l + r >> 1;
    int ans = 0;
    if(L<=m)
        ans += query(L,R,lson);
    if(R>m)
        ans += query(L,R,rson);
    return ans;
}

void init()
{
    memset(num,0,sizeof(num));
}

int Q,p,e,k,n;
int main()
{
    while(scanf("%d",&Q)!=EOF)
    {
        init();
        while(Q--)
        {
            scanf("%d%d",&p,&e);
            if(!p)
                update(e,1,1,N,1);
            else if(p==1)
                update(e,-1,1,N,1);
            else
            {
                scanf("%d",&k);
                n = query(1,e,1,N,1);
                k += n;
                n = query(k,1,N,1);
                if(n!=-1)
                    printf("%d
",n);
            }
        }
    }
    return 0;
}