ZOJ Monthly, August 2012 - C : Cinema in Akiba

問題概要

1~N(N<10^5)の座席があり、最初は全部空である。i人目の客は左からa[i]番目の空席に座る。各人がどの座席に座ったか求める問題。

解法

BITを使う典型問題。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

BinaryIndexedTree bitree;

const int MAX_N = 50000;
const int MAX_Q = 3000;

int N, Q;
int Qs[MAX_Q], as[MAX_N], ans[MAX_N];

bool init() {
	if (scanf("%d", &N) == EOF) {
		return false;
	}

	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; ++i) {
		scanf("%d", Qs + i);
		--Qs[i];
	}

	return true;
}

void solve() {
	bitree.init(N);
	for (int i = 0; i < N; ++i) {
		bitree.add(i, 1);
	}
	for (int i = 0; i < N; ++i) {
		ans[i] = bitree.getOverSumIndex(as[i] - 1);
		bitree.add(ans[i], -1);
	}

	for (int i = 0; i < Q; ++i) {
		printf("%d%c", ans[Qs[i]] + 1, i == Q-1 ? '\n': ' ');
	}
}

int main() {
	for (;init();) {
		solve();
	}
	return 0;
}