HDU 2852 KiKi's K-Number 树状数组

先补充从n个数中求第k小数的理论知识。。。。。。。。

睡觉去~

------------------------------------------又要睡觉的分割线------------------------------------------

HDU:http://acm.hdu.edu.cn/showproblem.php?pid=2852

题目大意，给定三种操作：

0 a代表插入一个数

1 a代表删除掉a这个数

2 a k 查询比a大的第k个数

跟着大神走~树状数组+二分

树状数组更新的求和的时间都只要log(n)

#include<cstdio>

#include<cstring>

const int MAXN=100000+10;

int data[MAXN];      //设置data为统计比该下标小的元素个数

inline int lowbit(int x)

{

	return x&(-x);

}

int sum(int x)

{

	int res=0;

	while(x>0)

	{

		res+=data[x];

		x-=lowbit(x);

	}

	return res;

}

void add(int id,int t)

{

	while(id < MAXN)

	{

		data[id]+=t;

		id+=lowbit(id);

	}

}

void findk(int x,int k)   // >=x kth number

{

	int L=x+1;

	int R=MAXN;

	int cur_sum=sum(x);

	while(L<R)

	{

		int mid=(L+R)>>1;   //这里并不会越界

		int mid_sum=sum(mid);

		if(mid_sum - cur_sum < k)

			L=mid+1;

		else

			R=mid;

	}

	if(L==MAXN)

	   printf("Not Find!\n");

   else

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

}

int main()

{

	int T;

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

	{

		memset(data,0,sizeof(data));

		while(T--)

		{

			int action,temp;

			scanf("%d%d",&action,&temp);

			if(action==0) //push

			{

				add(temp,1);

			}

			else if(action==1) //pop

			{

				if(sum(temp)==sum(temp-1))

					printf("No Elment!\n");

				else

					add(temp,-1);

			}

			else if(action==2)   //query

			{

				int k;

				scanf("%d",&k);

				findk(temp,k);

			}

		}

	}

	return 0;

}

巴特西

HDU 2852 KiKi's K-Number 树状数组

最新文章

热门文章