程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu2852--KiKi's K-Number(線段樹,求第k個數)

hdu2852--KiKi's K-Number(線段樹,求第k個數)

編輯:C++入門知識

hdu2852--KiKi's K-Number(線段樹,求第k個數)


KiKi's K-Number

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2546 Accepted Submission(s): 1174


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
If p is 1, then there will be an integer e (0
If p is 2, then there will be two integers a and k (0


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!

三種操作,0 代表添加一個數x,1代表刪除一個數x,2代表 找比a大的第k個數,使用線段樹求解,線段樹統計在一個區間內出現的數的個數,對於找比a大的第k個數,從a開始向後查找,如果在某段中累加的和大於k,就讓它跳入這段中,直到深入到一個葉子節點時,剛好ans >= k。

對線段樹的更新不解釋,主要是查詢的時候

1.如果當前區間[l,r]中 r<=a那麼這一段的數都不用統計。

2.如果r >a,代表該段中存在比a大的數就要向下深入。

3.如果l > a,那麼該段中所有的點都會大於a,開始判斷,如果該段全部加入後仍然小於k,那麼就可以全部加入,如果加進去以後大於等於k,那麼就要向下深入,一直深入到葉子節點,滿足條件的,最左的葉子節點就是我們要求的值。(線段樹,從左向右查找,一定可以找到第一個)

#include 
#include 
#include 
using namespace std;
#define maxn 110000
#define lmin 1
#define rmax n
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define now l,r,rt
#define int_now int l,int r,int rt
int cl[maxn<<2] , k1[maxn] , k2[maxn<<2] , top ;
void push_up(int_now)
{
    cl[rt] = cl[rt<<1] + cl[rt<<1|1] ;
}
void creat(int_now)
{
    cl[rt] = 0 ;
    if(l != r)
    {
        creat(lson);
        creat(rson);
        push_up(now);
    }
    else
    {
        cl[rt] = 0 ;
        k2[rt] = ++top ;
    }
}
void update(int x,int d,int_now)
{
    if( l > x || r < x )
        return ;
    if( l == r && l == x )
    {
        cl[rt] += d ;
        return ;
    }
    update(x,d,lson);
    update(x,d,rson);
    push_up(now);
}
int query(int ll,int ans,int num,int_now)
{
    if( r <= ll )
        return 0;
    if( ll < l )
    {
        if( ans + cl[rt] < num )
        return ans + cl[rt] ;
        if(ans < num && ans + cl[rt] >= num && l == r )
        {
            printf("%d\n", k2[rt] );
            return ans + cl[rt] ;
        }
        if(ans < num && ans + cl[rt] >= num )
        {
            if( ans + cl[rt<<1] >= num )
                ans = query(ll,ans,num,lson);
            else
                ans = query(ll,ans+cl[rt<<1],num,rson);
            return ans ;
        }
    }
    else
    {
        if( ans < num )
            ans = query(ll,ans,num,lson);
        if(ans < num)
            ans = query(ll,ans,num,rson);
        return ans;
    }
}
int main()
{
    int m , i , n , l , r , x , temp , num ;
    while(scanf("%d", &m) != EOF)
    {
        top = 0 ;
        n = maxn ;
        creat(root);
        memset(k1,0,sizeof(k1));
        while(m--)
        {
            scanf("%d", &temp);
            if( temp == 0 )
            {
                scanf("%d", &x);
                k1[x]++ ;
                update(x,1,root);
            }
            else if( temp == 1 )
            {
                scanf("%d", &x);
                if( k1[x] == 0 )
                    printf("No Elment!\n");
                else
                {
                    k1[x]-- ;
                    update(x,-1,root);
                }
            }
            else
            {
                scanf("%d %d", &l, &num);
                x = query(l,0,num,root);
                if(x < num)
                    printf("Not Find!\n");
            }
        }
    }

}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved