HDU2852【树状数组+二分】

额。。有点遗忘了树状数组特性了。。印象中一直是前缀和，然后一定要记住树状数组是把给出的值（值太大可能可以离散化）也就是点到了区间，然后这个点存的值就是由自己来定了。

题意：

百度。

思路：

树状数组是用来标记的！值->区间点！

因为这里值重复是算的，所有树状数组存的是区间上该位置的个数。

0：插入则插入。

1：if(!(sum[x]-sum[x-1])) puts("NO...");

2：我们知道a（包括a）之前有多少个数x，求第k大的数，也就是求在树状数组中第x+k大的数。

sum[ans]=x+k。这个可以直接二分查找。

---

哦，还可以线段树，还是一样的，值->区间点，点所存的值自己定，这里也就是个数，差不多。但是这个查找第k大的数的位置，麻烦了。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=1e5+10;

int c[N],m;

int lowbit(int x)

{

    return x&(-x);

}

void add(int x,int val)

{

    while(x<=100000)

    {

        c[x]+=val;

        x+=lowbit(x);

    }

}

int sum(int x)

{

    int ans=0;

    while(x>0)

    {

        ans+=c[x];

        x-=lowbit(x);

    }

    return ans;

}

int main()

{

    while(~scanf("%d",&m))

    {

        int x;

        int a,k;

        memset(c,0,sizeof(c));

        while(m--)

        {

            scanf("%d",&x);

            if(x==0)

            {

                scanf("%d",&a);

                add(a,1);

            }

            else if(x==1)

            {

                scanf("%d",&a);

                if(sum(a)-sum(a-1)==0)

                    puts("No Elment!");

                else

                    add(a,-1);

            }

            else

            {

                scanf("%d%d",&a,&k);

                int p=sum(a)+k;

                int left=1,right=100000;

                while(left<right)

                {

                    int mid=left+(right-left)/2;

                    if(sum(mid)>=p)

                        right=mid;

                    else

                        left=mid+1;

                }

                if(sum(left)>=p)

                    printf("%d\n",left);

                else

                    puts("Not Find!");

            }

        }

    }

    return 0;

}

巴特西

HDU2852【树状数组+二分】

最新文章

热门文章