天体観測 [パソコン甲子園2014 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0302?year=2014

考察過程

1. 何を全探索すれば効率良く計算ができるかを考える
2. bの範囲の下限を全探索すると、明るさが[b,b+d]である頂点のx座標の最大最小、y座標の最大最小が高速に求まれば良さそう
3. bの大きさでソートしておけば、セグメントツリーでできそう
4. bだけのソート済み配列があれば、セグメントツリーの座標が取ってこれる

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0302/judge/3161123/C++14

bの範囲の下限を全探索することにする。
明るさが[b,b+d]である頂点のx座標の最大最小、y座標の最大最小を高速に求める手段を考える。
　
まず、全ての頂点をbの大きさでソートする。
tupleを使って、1番目をb, 2番目をx, 3番目をyとしてソートする。
すると、1番目の大小関係でまずソートされるので、bの大きさでソートすることができる。
　
つぎに、bだけの配列を作ってソートする
この配列を見ると、全ての頂点のソート列とbの大きさは一致する。
　
これで、明るさ[b,b+d]の範囲は、lower_boundでb以上となる初めての添字がL,
upper_boundでb+dより大きくなる初めての添字がRとすると、[L,R)となる。
あとは、[L,R)の範囲のx,y座標の最大最小を高速に求める方法だが、これはセグメントツリーを使うとできる。
計算量はO(NlogN)で間に合う。

※ 尺取法とSparse Tableを使うことでO(N)を実現することもできる

struct Node {
    int sx, tx, sy, ty;
    Node() { sx = inf; tx = -inf; sy = inf; ty = -inf; }
    Node(int _sx, int _tx, int _sy, int _ty) { sx = _sx, tx = _tx, sy = _sy, ty = _ty; }
};
using V = Node;
#define def Node()
template<int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { 
        return Node(min(l.sx, r.sx), max(l.tx, r.tx), min(l.sy, r.sy), max(l.ty, r.ty));
    };

    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
        auto a = get(x, y, l, (l + r) / 2, k * 2);
        auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
        return comp(a, b);
    }
    void update(int i, V v) {
        i += NV; val[i] = v;
        while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
    }
    V operator[](int x) { return get(x, x + 1); }
};


int N, d;
tuple<int, int, int> points[201010];
int bv[201010];
SegTree<1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> d;
    rep(i, 0, N) {
        int x, y, b; cin >> x >> y >> b;
        points[i] = make_tuple(b, x, y);
        bv[i] = b;
    }
    sort(points, points + N);
    sort(bv, bv + N);

    rep(i, 0, N) {
        int x, y, b;
        tie(b, x, y) = points[i];
        st.update(i, Node(x, x, y, y));
    }
    
    ll ans = 0;
    rep(i, 0, N) {
        int L = i;
        int R = upper_bound(bv, bv + N, bv[i] + d) - bv;

        auto no = st.get(L, R);

        ll sx = no.sx;
        ll tx = no.tx;
        ll sy = no.sy;
        ll ty = no.ty;
        chmax(ans, (tx - sx) * (ty - sy));
    }
    cout << ans << endl;
}