verify/Datastructure_2dsegtree_max.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/1068

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1068"
#include "../Utility/template.hpp"

#include "../Datastructure/2dsegtree.hpp"

using S = int;
S op(S l, S r) {
    return min(l, r);
}

S e() {
    return INT_MAX;
}

int main() {
    int r, c, q;
    while(cin >> r >> c >> q) {
        if(r==0) break;

        vec<vec<int>> grid(r, vec<int>(c));
        rep(i, 0, r) rep(j, 0, c) cin >> grid[i][j];
    
        segtree2d<S, op, e> seg(r, c);
        rep(i, 0, r) rep(j, 0, c) seg.preset(i, j, grid[i][j]);
        seg.build();
        while(q--) {
            int sy, sx, ty, tx;
            cin >> sy >> sx >> ty >> tx;
            cout << seg.prod(sy, ty+1, sx, tx+1) << '\n';
        }
    }
}

#line 1 "verify/Datastructure_2dsegtree_max.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1068"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 3 "verify/Datastructure_2dsegtree_max.test.cpp"

#line 1 "Datastructure/2dsegtree.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct segtree2d {
    int id(int y, int x) {return y * 2 * W + x;} //= y番目のセグ木の、ノードxに対応する添字
    int H, W;
    vec<S> dat;
    bool f;

    segtree2d(int h, int w) {
        f = true;
        H = W = 1;
        while(H < h) H <<= 1;
        while(W < w) W <<= 1;
        dat.resize(4 * H * W, e());
    }

    void preset(int y, int x, S v) {f = false,  dat[id(y + H, x + W)] = v; }

    void build() {
        f = true;
        rep(h, H, 2 * H) {
            rrep(w, 1, W) {
                dat[id(h, w)] = op(dat[id(h, 2 * w)], dat[id(h, 2 * w + 1)]);
            }
        }
        
        rrep(h, 0, H) {
            rrep(w, 1, 2 * W) {
                dat[id(h, w)] = op(dat[id(h * 2, w)], dat[id(h * 2 + 1, w)]);
            } 
        }
    }

    void set(int y, int x, S v) {
        assert(f);

        y += H, x += W;
        dat[id(y, x)] = v;
        rrep(w, 1, W) {
            dat[id(y, w)] = op(dat[id(y, 2 * w)], dat[id(y, 2 * w + 1)]);
        }

        while(y > 1) {
            y >>= 1;
            for(int j = x; j >= 1; j >>= 1) {
                dat[id(y, j)] = op(dat[id(y * 2, j)] , dat[id(y * 2 + 1, j)]);
            }
        }
    }

    S inner(int h, int l, int r) {
        S sml = e(), smr = e();
        l += W, r += W;
        while(l < r) {
            if(l & 1) sml = op(sml, dat[id(h, l++)]);
            if(r & 1) smr = op(dat[id(h, --r)], smr);
            l >>= 1, r >>= 1;
        }
        return op(sml, smr);
    }

    S prod(int sy, int ty, int sx, int tx) {
        assert(f);

        S sml = e(), smr = e();
        sy += H, ty += H;
        while(sy < ty) {
            if(sy & 1) sml = op(sml, inner(sy++, sx, tx));
            if(ty & 1) smr = op(inner(--ty, sx, tx), smr);
            sy >>= 1, ty >>= 1;
        }
        return op(sml, smr);
    }

    S get(int y, int x) {
        return dat[id(y + H, x + W)];
    }
};
/*
@brief 2次元セグメント木
@docs doc/2dseg_small.md
*/
#line 5 "verify/Datastructure_2dsegtree_max.test.cpp"

using S = int;
S op(S l, S r) {
    return min(l, r);
}

S e() {
    return INT_MAX;
}

int main() {
    int r, c, q;
    while(cin >> r >> c >> q) {
        if(r==0) break;

        vec<vec<int>> grid(r, vec<int>(c));
        rep(i, 0, r) rep(j, 0, c) cin >> grid[i][j];
    
        segtree2d<S, op, e> seg(r, c);
        rep(i, 0, r) rep(j, 0, c) seg.preset(i, j, grid[i][j]);
        seg.build();
        while(q--) {
            int sy, sx, ty, tx;
            cin >> sy >> sx >> ty >> tx;
            cout << seg.prod(sy, ty+1, sx, tx+1) << '\n';
        }
    }
}