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; }