值域线段树求第k大

题目让你实现一种容器支持3个操作：

1. 0 x:把x插入容器中
2. 1 x:把x从容器中删除，如果有相同的多个，则只删除一个，如果容器中没有要删除的元素，就输出No Elment!
3. 2 x k:求这个容器中大于x这个数的第k个元素的值\

我们可以开一个线段树来维护，插入和删除就相当于在线段树的对应位置上给权值+1或者-1，重要的是如何求大于x的第k个元素，我们可以先求出小于等于x的数有多少个(cnt)，然后问题就转化成了，在整个容器中，第cnt+k个元素的值是多少。

第k大:如1 2 3 3 3 4 4 5第4大的数是3，第5大的数还是3

代码:

#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int sum[N << 2], vis[N];
void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int p, int add, int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] += add;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
        update(p, add, lson);
    else
        update(p, add, rson);
    pushup(rt);
}
int query(int k, int l, int r, int rt) //求整个线段树中第k大
{
    if (l == r)
        return l;
    int m = (l + r) >> 1;
    if (sum[rt << 1] >= k)
        return query(k, lson);
    return query(k - sum[rt << 1], rson);
}
int Rank(int p, int l, int r, int rt) //<=p的数出现的总次数
{
    if (p >= r)
        return sum[rt];
    int m = (l + r) >> 1;
    int ans = 0;
    ans += Rank(p, lson);
    if (m <= p - 1)
        ans += Rank(p, rson);
    return ans;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    int n;
    while (~scanf("%d", &n))
    {
        mem(vis, 0);
        int op, x, k;
        build(1, N, 1);
        while (n--)
        {
            scanf("%d", &op);
            if (op == 0)
            {
                scanf("%d", &x);
                update(x, 1, 1, N, 1);
                vis[x]++;
            }
            else if (op == 1)
            {
                scanf("%d", &x);
                if (!vis[x])
                    puts("No Elment!");
                else
                {
                    update(x, -1, 1, N, 1);
                    vis[x]--;
                }
            }
            else if (op == 2)
            {
                scanf("%d%d", &x, &k);
                int ans = Rank(x, 1, N, 1); //查找<=x的数个个数
                if (sum[1] < ans + k)
                    puts("Not Find!");
                else
                    printf("%d\n", query(ans + k, 1, N, 1));
            }
        }
    }
    return 0;
}