POJ 3109: Inner Vertices

概要

2次元格子上においてある黒い石の情報が与えられる．
ある格子点において，x方向，y方向共に黒い石に挟まれているならそこにも黒い石を置く．
最終的に格子上においてある黒い石の個数はいくつか？

解法

扱いやすいように座標圧縮をしておく．
各x座標について，そのx座標をもつ最小(最大)のy座標を計算．
y座標についても同様の操作を行う．この時，「同じy座標をもつ中で最小（最大）のx座標の点で線分の追加（削除）をする」というイベントにして管理する．

x座標の小さい方から，縦方向の範囲をBITに足しこむ．線分の追加・削除のところで点の個数をカウントするとうまくいく．

コードが雑で，変な使い回しをしているためわかりにくい．

typedef int Type;
struct Fenwick{
    vector<Type> bit;
    Fenwick(int n){
        bit = vector<Type>(n + 1);
    }
    void update(int i, Type v){
        int n = bit.size();
        ++i;
        while(i <= n){
            bit[i] += v;
            i += i & -i;
        }
    }
    Type get(int i){
        Type res = 0;
        ++i;
        while(i > 0){
            res += bit[i];
            i -= i & -i;
        }
        return res;
    }
};

int n, nx, ny;
pair<int, int> p[200010];
int xl[100010], yl[100010];
int sx[100010], sy[100010];
int ex[100010], ey[100010];
Fenwick bit(100010);
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", xl+i, yl+i);
        p[i] = make_pair(xl[i], yl[i]);
    }
    sort(xl, xl+n);
    nx = unique(xl, xl+n) - xl;
    sort(yl, yl+n);
    ny = unique(yl, yl+n) - yl;

    for(int i = 0; i < n; ++i){
        sx[i] = sy[i] = 200010;
        ex[i] = ey[i] = 0;
    }
    for(int i = 0; i < n; ++i){
        p[i].first = lower_bound(xl, xl+nx, p[i].first) - xl;
        p[i].second = lower_bound(yl, yl+ny, p[i].second) - yl;
        sy[p[i].first] = min(sy[p[i].first], p[i].second);
        ey[p[i].first] = max(ey[p[i].first], p[i].second);
        sx[p[i].second] = min(sx[p[i].second], p[i].first);
        ex[p[i].second] = max(ex[p[i].second], p[i].first);
    }
    for(int i = 0; i < ny; ++i){
        p[2*i] = make_pair(sx[i], i);
        p[2*i+1] = make_pair(ex[i], i+ny);
    }
    ll cnt = 0;
    int idx = 0;
    sort(p, p+ny*2);
    for(int i = 0; i < nx; ++i){
        while(idx < ny * 2 && p[idx].first == i && p[idx].second < ny){
            int y = p[idx].second;
            cnt -= bit.get(y);
            ++idx;
        }
        bit.update(sy[i], 1);
        bit.update(ey[i]+1, -1);
        while(idx < ny * 2 && p[idx].first == i){
            int y = p[idx].second - ny;
            cnt += bit.get(y);
            ++idx;
        }
    }
    printf("%d\n", cnt);
    return 0;
}