POJ-3109 : Inner Vertices

問題概要

2次元格子上にn(<10^5)個の黒い点がある。上下左右に黒い点がある格子点は黒に変わる。十分時間が立った後黒い点はいくつあるか求める問題。

解法

とりあえず座標圧縮しておく。y座標の小さい点から順に処理をしていく。数え方としては、蓋をするときにまとめてカウントする感じ。区間に数字を足し込む操作があるのでBITを使って頑張る。

acceptされたコード

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

typedef long long int64;
const int MAX_N = int(1e5);

typedef int64 bit_t;

struct RangeSumQuery {
	int size;
	BinaryIndexedTree bit0, bit1;

	RangeSumQuery(){}

	void init(int size_) {
		size = size_;
		bit0.init(size);
		bit1.init(size);
	}

	//[0, n)
	bit_t getSum(int n) {
		return bit0.getSum(n) + bit1.getSum(n) * n;
	}

	//[from, to)
	bit_t getSum(int from, int to) {
		return getSum(to) - getSum(from);
	}

	//[from, to)
	void add(int from, int to, bit_t value) {
		bit0.add(to, to * value);
		bit0.add(from, - from * value);
		bit1.add(from, value);
		bit1.add(to, -value);
	}
};

int N, X, Y;
int xs[MAX_N], ys[MAX_N], nums[MAX_N];
bool covered[MAX_N];
vector<int> bs[MAX_N];

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d%d", xs+i, ys+i);
	}
}

void compress(int as[], int &L) {
	for (int i = 0; i < N; ++i) {
		nums[L++] = as[i];
	}
	sort(nums, nums + L);
	L = unique(nums, nums + L) - nums;
	for (int i = 0; i < N; ++i) {
		as[i] = lower_bound(nums, nums + L, as[i]) - nums;
	}
}

int64 solve() {
	compress(xs, X);
	compress(ys, Y);
	for (int i = 0; i < N; ++i) {
		bs[ys[i]].push_back(xs[i]);
	}

	static RangeSumQuery rsq;
	rsq.init(X);
	int64 ans = N;
	for (int y = 0; y < Y; ++y) {
		sort(bs[y].begin(), bs[y].end());
		for (int i = 0; i < int(bs[y].size()); ++i) {
			const int x = bs[y][i];
			const int64 s = rsq.getSum(x, x+1);
			if (covered[x]) {
				ans += s;
			}
			covered[x] = true;
			rsq.add(x, x+1, -s);
			if (i + 1 < int(bs[y].size())) {
				rsq.add(x + 1, bs[y][i+1], 1);
			}
		}
	}

	return ans;
}

int main() {
	init();
	printf("%lld\n", solve());
	return 0;
}