hdu2852KiKi's K-Number【线段树第k小】

Total Submission(s): 3314    Accepted Submission(s): 1487

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 <e <100000), means press element e into Container.

If p is 1, then there will be an integer e (0 <e <100000), indicated that delete the element e from the container  

If p is 2, then there will be two integers a and k (0 <a <100000, 0 <k <10000),means the inquiries, the element is greater than a, and the k-th larger number.

 

Output

For each deletion, if you want to delete the element which does not exist, the output "No Elment!". For each query, output the suitable answers in line .if the number does not exist, the output "Not Find!".

 

Sample Input

   
   5
0 5
1 2
0 6
2 3 2
2 8 1
7
0 2
0 2
0 4
2 1 1
2 1 2
2 1 3
2 1 4
  
  

 

Sample Output

   
   No Elment!
6
Not Find!
2
2
4
Not Find!
  
  

 

Source

2009 Multi-University Training Contest 4 - Host by HDU

 

其实最开始发现这是一个用线段树解决的第k大，我是拒绝的，然而划分树毕竟还是不熟，更何况这题划分树也做不了，线段树虽说麻烦，但是什么问题都能解决。话说杭电的多校怎么都是kiki而且线段树数组怎么需要开那么大才不会RE啊

比较简单的简单的做法是不仅写build  update query还写一个求sum的函数，由于题目要求在容器中比a大的第b小个数值，，我们想到应该先求a是整个容器中第几小的。说一下query函数的意义：剩余个数大于左子树个数：如果到达叶子节点，输出端点值；没到叶节点，进入右子树，剩余个数减少。剩余个数大于左子树，肯定进入左子树。val值域是范围个数居然没想到==

关于判断是否存在第b小的值：假设这个值不存在，我们每次都是进入第一个if，然后进入右子树，循环往复，那么tmp一定就是10000啦

/************
hdu2825
2016.3.8
982MS	7888K	2122 B	C++
************/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    int l,r,tot;
}num[800000];
int tmp;
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,bool flag)///1:add 0:del
{
    if(num[rt].l==num[rt].r)
    {
        if(flag) num[rt].tot++;
        else num[rt].tot--;
        return;///!!!
    }
    int mid=(num[rt].l+num[rt].r)/2;
    if(pos<=mid) update(rt<<1,pos,flag);
    else update(rt<<1|1,pos,flag);
    num[rt].tot=num[rt<<1].tot+num[rt<<1|1].tot;
}
int sum(int rt,int l,int r)
{
    if(num[rt].r<l||num[rt].l>r) return 0;
    if(num[rt].r<=r&&num[rt].l>=l) return num[rt].tot;
    int mid=(num[rt].l+num[rt].r)/2;
    return sum(rt<<1,l,r)+sum(rt<<1|1,l,r);
}
void query(int rt,int ans)
{
    if(ans>num[rt<<1].tot)
    {
        if(num[rt].l==num[rt].r)
        {
            tmp=num[rt].r;
            return;
        }
        query(rt<<1|1,ans-num[rt<<1].tot);
    }
    else query(rt<<1,ans);
}
int main()
{
  //  freopen("cin.txt","r",stdin);
    int q,a,b,m;
    while(~scanf("%d",&m))
    {
        build(1,1,100000);
        while(m--)
        {
            scanf("%d",&q);
            if(q==0)
            {
                scanf("%d",&a);
                update(1,a,1);
            }
            else if(q==1)
            {
                scanf("%d",&a);
                if(sum(1,1,a)==sum(1,1,a-1)) printf("No Elment!\n");
                else update(1,a,0);
            }
            else
            {
                scanf("%d%d",&a,&b);
                {
                    int t=sum(1,1,a);
                    tmp=0;
                    query(1,t+b);
                    if(tmp==100000)printf("Not Find!\n");
                    else printf("%d\n",tmp);
                }
            }
        }
    }
    return 0;
}