（树状数组）KiKi's K-Number -- HDOJ

83 阅读 0 评论 55 点赞

我是靠谱客的博主瘦瘦指甲油，最近开发中收集的这篇文章主要介绍（树状数组）KiKi's K-Number -- HDOJ，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

KiKi’s K-Number
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 229 Accepted Submission(s): 94

Problem Description
For the k-th number, we all should be very familiar with it. Of course,to kiki it is also simple. Now Kiki meets a very similar problem, kiki wants to design a container, the container is to support the three operations.

Push: Push a given element e to container

Pop: Pop element of a given e from container

Query: Given two elements a and k, query the kth larger number which greater than a in container;

Although Kiki is very intelligent, she can not think of how to do it, can you help her to solve this problem?

Input
Input some groups of test data ,each test data the first number is an integer m (1 <= m <100000), means that the number of operation to do. The next m lines, each line will be an integer p at the beginning, p which has three values:
If p is 0, then there will be an integer e (0

/*
   1、插入一个数，add(x,1)在x位置插入一个1，相当于x位置多了一个数
      代表x这个数出现了几次
   2、sum(i) 代表 小于等于i的个数有多少个，那么找一个数是否存在，就
      今天可以用sum(i) - sum(i-1) 来判断i出现的次数
      删除一个数用add(x,-1)即可
   3、先找到sum(i)，也就是小于等于i的个数，那么第y+sum(i)个数就是比
      i大的第y个数
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

const int maxn=100010;
int c[maxn];
int n;

int lowbit(int x)
{
    return x&(-x);
}
void add(int i,int val)
{
    while(i<=maxn)
    {
        c[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
//求第k个数
int getkth2(int k)
{
    int l=0,r=maxn,mid,f;
    while(l<r-1)
    {
        mid=(l+r)>>1;
        f=sum(mid);
        if(f>=k) r=mid;
        else l=mid;
    }
    return r;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int m;
    while(scanf("%d",&m) != EOF)
    {
        memset(c,0,sizeof(c));
        int op,x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&op);
            if(op == 0)
            {
                scanf("%d",&x);
                //x位置加一，相当于，插入了一个值为x 的数
                //sum(i)就代表小于等于i的个数
                add(x,1);
            }
            else if(op == 1)
            {
                scanf("%d",&x);
                if(sum(x) - sum(x-1) == 0)
                    cout << "No Elment!"<<endl;
                else
                    add(x,-1);//
            }
            else if(op == 2)
            {
                scanf("%d %d",&x,&y);
                if(sum(maxn-1) - sum(x) < y) // 大于x的个数
                    cout << "Not Find!"<<endl;
                else
                {

                    printf("%dn",getkth2(y+sum(x)));
                }
            }
        }
    }

    return 0;
}