程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU2852 KiKi&#39;s K-Number 樹狀數組+二分

HDU2852 KiKi&#39;s K-Number 樹狀數組+二分

編輯：C++入門知識

這題就是給了你三種操作，

1：往容器中一個元素 x

2:：把容器中的元素x刪除

3：查詢比 x大的第k個數

想法：添加元素跟刪除元素直接是以數本身為序號然後以 value值為1和-1即可，相當於計數，至於找比x第k個大的數，那就看看當前往後數k個數的第一個數是哪個就可以了，一開始直接找出來，然後往後暴力的掃了一遍，結果錯了，沒關系，反應很快，直接改了個二分查找，然後就過了，弄清楚如何建立這個樹狀數組即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;

const int N = 100000 + 10;

int n;

int c[N];

void clear() {
	memset(c,0,sizeof(c));
}

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

//設原始矩陣為a,將a[i]加上val時對c所做的修改
void add(int i, int val) {
	while (i <= N) {
		c[i] += val;
		i += lowbit(i);
	}
} 

//求前i項元素的和
int get_sum(int i) {
	int sum = 0;
	while (i > 0) {
		sum += c[i];
		i -= lowbit(i);
	}
	return sum;
}

void cal(int a,int k) {
	int sum = get_sum(a);
	bool flag = false;
	int l = a + 1;
	int r = N;
	while(l < r) {
		int mid = (l + r)/2;
		int tmp = get_sum(mid);
		if(tmp < sum + k)
			l = mid + 1;
		else
			r = mid;
	}
	if(get_sum(l) >= k + sum) {
		printf("%d\n",l);
	}
	else
		puts("Not Find!");
}

int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		clear();
		int x;
		for(int i=0;i