hdu2852KiKi's K-Number 樹狀數組和二分查找

//題意：有一個容器可以增，删，查找,删除時若不存在則輸入No Element，查找時不存在則輸入Not Find;

//利用樹狀數組和二分查找解決

//首先利用樹狀數組儲存其數組元素的狀态，若a存在則getSum(a) - getSum(a - 1)必須大于0,因為a > 0

//若a不存在，則更新樹狀數組

//查找的時候利用二分查找，這裡注意由于我們是查找比a大的第k個元素，是以并不能像原來的二分查找那樣，找到k=getSum(x) - getSum(a)就立刻傳回

//因為有可能x是不存在的，是以我們隻能找到滿足k=getSum(x) - getSum(a)的最小的x傳回，這樣x才是找到的值

#include <iostream>
#include <algorithm>
using namespace std;

#define NSIZ 100200
int tree[NSIZ];

int lowbit(int i)
{
	return i&(-i);
}

int getSum(int i)
{
	int sum = 0;
	while(i >= 1)
	{
		sum += tree[i];
		i -= lowbit(i);
	}

	return sum;
}

void update(int i, int x)
{
	while(i <= NSIZ)
	{
		tree[i] += x;
		i += lowbit(i);
	}
}

void binarySearch(int a, int k)
{
	int left = a + 1, right = NSIZ;
	int num1 = getSum(a), num2 = 0;
	int mid = 0;
	while(left <= right)
	{
		mid = left + (right - left) / 2;
		num2 = getSum(mid);
		if (num2 - num1 < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}

	}

	if (left >= NSIZ)
	{
		printf("Not Find!\n");
	}
	else
	{
		printf("%d\n", left);
	}

}

int main()
{
	int i, j, p, m;
	int a, k, e;
	while(scanf("%d", &m) != EOF)
	{
		memset(tree, 0, sizeof(tree));

		for (i = 0;i < m; ++i)
		{
			scanf("%d", &p);
			switch(p)
			{
			case 0:
				{
					
					scanf("%d", &e);
					update(e, 1);

				}
				break;
			case 1:
				{
					
					scanf("%d", &e);
					if (getSum(e) - getSum(e-1) == 0)
					{
						printf("No Elment!\n");
					}
					else
					{
						update(e, -1);
					}
				}
				break;
			case 2:
				{
					scanf("%d %d", &a, &k);
					binarySearch(a, k);
				}
				break;
			default:
				break;
			}
		}
	}
	return 0;
}