hdu 4217 Data Structure?(树状数组）

题目链接：hdu 4217 Data Structure?

题目大意：给出n和m，表示有n个数1~n，然后每次从这个集合中挑选出第ki个小的（m次），问说挑选出来的数字的和。

解题思路：树状数组，v记录的即为其区间上有多少个数未选取，进行取操作的时候只要找到第x个，使得前面的和刚好是ki即可。

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

const int N = 270000;
typedef long long ll;

int n, m;
ll v[N];

void add(int x, int val) {
	while (x <= n) {
		v[x] += val;
		x += (x & (-x));
	}
}

void init() {
	scanf("%d%d", &n, &m);
	memset(v, 0, sizeof(v));
	for (int i = 1; i <= n; i++) add(i, 1);
}

int sum(int k) {
	int x = 0, s = 0;

	for (int i = 18; i >= 0; i--) {
		if (x + (1<<i) < n && s + v[x+ (1<<i)] < k) {
			x += (1<<i);
			s += v[x];
		}
	}
	return x+1;
}

ll solve() {
	int k;
	ll ans = 0;

	for (int i = 0; i < m; i++) {
		scanf("%d", &k);
		int s = sum(k);
		ans += s;
		add(s, -1);
	}
	return ans;
}

int main() {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		init();
		cout << "Case " << i <<": " << solve() << endl;
	}
	return 0;
}

hdu 4217 Data Structure?(树状数组）

原文：http://blog.csdn.net/keshuai19940722/article/details/18850575