1216.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1216 on 2006-01-28 at 12:51:20 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 10240;

int ulmt, dlmt;

class TreeArray {
private:
	int in[MAX], count[MAX];
	inline int lowBit(int) const;
public:
	void make();
	void add(int, int);
	bool find(int);
	int pos(int);
};
inline int TreeArray::lowBit(int t) const {
	return t & (-t);
}
void TreeArray::add(int o, int a) {
	count[o] += a;
	if(o != 0)
		for(; o <= ulmt; o += lowBit(o)) in[o] += a;
}
void TreeArray::make() {
	memset(in, 0, sizeof(in)); memset(count, 0, sizeof(count));
}
bool TreeArray::find(int n) {
	return count[n] != 0;
}
int TreeArray::pos(int n) {
	add(n, -1); int sum = 1;
	if(n != 0) sum += count[0];
	for(n = n-1; n >= dlmt; n -= lowBit(n)) sum += in[n];
	return sum;
}

int main()
{
	int n, m, mar[MAX];
	int t, i;
	TreeArray marble;
	
	for(t = 1; scanf("%d %d", &n, &m) != EOF && !(n == 0 && m == 0); t++) {
		marble.make(); ulmt = -1; dlmt = MAX;
		for(i = 0; i < n; i++) scanf("%d", &mar[i]), ulmt = max(ulmt, mar[i]), dlmt = min(dlmt, mar[i]);
		if(dlmt == 0) dlmt = 1;
		for(i = 0; i < n; i++) marble.add(mar[i], 1);
		printf("CASE# %d:\n", t);
		for(i = 0; i < m; i++) {
			int k; scanf("%d", &k);
			if(marble.find(k)) printf("%d found at %d\n", k, marble.pos(k));
			else printf("%d not found\n", k);
		}
	}
	
	return 0;
}