hdu 2852 KiKi’s K-Number 题解【binary-lifting】【树状数组】

点击量：241

学到了一种树状数组上二分的方法。

目录

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 $ k$th 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\le 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

题意

有一个空的容器。$ \tt 0 e$表示往这个容器里放入一个元素$ e$；$ \tt 1 e$表示从这个容器里删除一个元素$ e$，如果这个元素不存在，输出No Elment!；$ \tt 2 a k$表示查询这个容器中比$ a$大的第$ k$个数，如果这个数不存在，输出Not Find!。

多组数据。

题解：

这个题$ 100000$的数据范围是可以用$O(n\log^2 n)$通过的。但是有些毒瘤出题人就喜欢卡两个$ \log$。

两个$ \log$做法

直接二分，每次用ask()函数求出前缀共有多少个元素。时间复杂度为$ O(n\log^2 n)$。

一个$ \log$做法

用一种叫做Binary Lifting的算法。这种做法来自于CF的一篇博客[Tutorial] by sdnr1，是一种在树状数组上二分的好方法。

如果要求比$ a$大的第$ k$个数，等价于求整个容器中第$ cnt[a]+k$小的数。$ cnt[a]$表示不超过$ a$的元素数量个数。

那么我们从零开始，从高位往低位枚举二进制位，如果这一位变成$ 1$后前缀和还是不超过$ cnt[a]+k$，这一位就一定可以变成$ 1$。

又因为是从高位开始枚举的，所以低位全部是$ 0$。假设当前二分到的位置是$ p$，现在枚举到的是第$ i$位，那么树状数组中$ c[p+2^i]$维护的就是$ sum[p+2^i]-sum[p]$。因此就像二分一样把左区间全部加上了。

Code：

#include<cstdio>
#include<cstring>
#define lowbit(x) (x&(-x))
#define N (1<<17)
int c[201000];//防止1<<17越界
void add(int p,int x)
{
    while(p<=N)
    {
        c[p]+=x;
        p+=lowbit(p);
    }
}
int ask(int p)
{
    int ans=0;
    while(p)
    {
        ans+=c[p];
        p-=lowbit(p);
    }
    return ans;
}
int main()
{
    int n,op,u,v;
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&op);
            if(op==0)
            {
                scanf("%d",&u);
                add(u,1);
            }
            else if(op==1)
            {
                scanf("%d",&u);
                if(ask(u)-ask(u-1)>0)
                    add(u,-1);
                else
                    puts("No Elment!");
            }
            else
            {
                scanf("%d%d",&u,&v);
                int t=ask(u)+v;
                if(t>ask(N))
                    puts("Not Find!");
                else
                {
                    int p=0,sum=0;
                    for(int j=17;j>=0;--j)
                        if(sum+c[p+(1<<j)]<t)
                        {
                            p+=(1<<j);
                            sum+=c[p];
                        }
                    printf("%d\n",p+1);
                }
            }
        }
    }
    return 0;
}