verify/aoj_other/aoj_1068.test.cpp

View this file on GitHub
Last update: 2024-07-13 11:37:49+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1068

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1068"

#include <bits/stdc++.h>

#include "algebra/monoid_s/monoid_min.hpp"
#include "data_structure/segment_tree_2d.hpp"

void solve(int R, int C, int Q) {
    std::vector<std::vector<int>> A(R, std::vector<int>(C));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            std::cin >> A[i][j];
        }
    }
    SegmentTree2D<MonoidMin<int>> seg(A);
    while (Q--) {
        int r1, c1, r2, c2;
        std::cin >> r1 >> c1 >> r2 >> c2;
        std::cout << seg.prod(r1, c1, r2 + 1, c2 + 1) << '\n';
    }
    return;
}

int main() {
    int R, C, Q;
    while (std::cin >> R >> C >> Q, !(R == 0 and C == 0 and Q == 0)) solve(R, C, Q);
    return 0;
}

#line 1 "verify/aoj_other/aoj_1068.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1068"

#include <bits/stdc++.h>

#line 2 "algebra/monoid_s/monoid_min.hpp"
// MS
template <class T> struct MonoidMin {
    using S = T;
    static constexpr S op(S a, S b) { return std::min(a, b); }
    static constexpr S e() { return std::numeric_limits<T>::max(); }
};
#line 2 "data_structure/segment_tree_2d.hpp"

template <class MS> struct SegmentTree2D {
   public:
    using S = typename MS::S;
    SegmentTree2D() : SegmentTree2D(0, 0) {}
    SegmentTree2D(int h, int w) : SegmentTree2D(std::vector<std::vector<S>>(h, std::vector<S>(w, MS::e()))) {}
    SegmentTree2D(const std::vector<std::vector<S>>& v) : h((int)(v.size())), w((int)(v[0].size())) {
        logh = 0;
        while ((1U << logh) < (unsigned int)(h)) logh++;
        sizeh = 1 << logh;
        logw = 0;
        while ((1U << logw) < (unsigned int)(w)) logw++;
        sizew = 1 << logw;
        d = std::vector<std::vector<S>>(sizeh << 1, std::vector<S>(sizew << 1, MS::e()));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                d[i + sizeh][j + sizew] = v[i][j];
            }
        }
        for (int i = sizeh - 1; i >= 1; i--) {
            for (int j = sizew; j < (sizew << 1); j++) {
                update_bottom(i, j);
            }
        }
        for (int i = 0; i < (sizeh << 1); i++) {
            for (int j = sizew - 1; j >= 1; j--) {
                update_else(i, j);
            }
        }
    }

    void set(int h, int w, const S& x) {
        assert(0 <= h and h < h and 0 <= w and w < w);
        h += sizeh;
        w += sizew;
        d[h][w] = x;
        for (int i = 1; i <= logh; i++) update_bottom(h >> i, w);
        for (int i = 0; i <= logh; i++) {
            for (int j = 1; j <= logw; j++) {
                update_else(h >> i, w >> j);
            }
        }
    }

    void chset(int h, int w, const S& x) {
        assert(0 <= h and h < h and 0 <= w and w < w);
        h += sizeh;
        w += sizew;
        d[h][w] = MS::op(d[h][w], x);
        for (int i = 1; i <= logh; i++) update_bottom(h >> i, w);
        for (int i = 0; i <= logh; i++) {
            for (int j = 1; j <= logw; j++) {
                update_else(h >> i, w >> j);
            }
        }
    }

    S operator()(int h, int w) const {
        assert(0 <= h and h < h and 0 <= w and w < w);
        return d[h + sizeh][w + sizew];
    }

    S get(int h, int w) const {
        assert(0 <= h and h < h and 0 <= w and w < w);
        return d[h + sizeh][w + sizew];
    }

    S inner_prod(int h, int w1, int w2) {
        S sml = MS::e(), smr = MS::e();
        while (w1 < w2) {
            if (w1 & 1) sml = MS::op(sml, d[h][w1++]);
            if (w2 & 1) smr = MS::op(d[h][--w2], smr);
            w1 >>= 1;
            w2 >>= 1;
        }
        return MS::op(sml, smr);
    }

    S prod(int h1, int w1, int h2, int w2) {
        assert(0 <= h1 and h1 <= h2 and h2 <= h);
        assert(0 <= w1 and w1 <= w2 and w2 <= w);
        S sml = MS::e(), smr = MS::e();
        h1 += sizeh;
        h2 += sizeh;
        w1 += sizew;
        w2 += sizew;

        while (h1 < h2) {
            if (h1 & 1) sml = MS::op(sml, inner_prod(h1++, w1, w2));
            if (h2 & 1) smr = MS::op(inner_prod(--h2, w1, w2), smr);
            h1 >>= 1;
            h2 >>= 1;
        }
        return MS::op(sml, smr);
    }

    S all_prod() const { return d[1][1]; }

    std::vector<std::vector<S>> make_vector() {
        std::vector vec(h, std::vector<S>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) vec[i][j] = get(i, j);
        }
        return vec;
    }

   private:
    int h, logh, sizeh, w, logw, sizew;
    std::vector<std::vector<S>> d;
    inline void update_bottom(int i, int j) { d[i][j] = MS::op(d[(i << 1) | 0][j], d[(i << 1) | 1][j]); }
    inline void update_else(int i, int j) { d[i][j] = MS::op(d[i][(j << 1) | 0], d[i][(j << 1) | 1]); }
};
#line 7 "verify/aoj_other/aoj_1068.test.cpp"

void solve(int R, int C, int Q) {
    std::vector<std::vector<int>> A(R, std::vector<int>(C));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            std::cin >> A[i][j];
        }
    }
    SegmentTree2D<MonoidMin<int>> seg(A);
    while (Q--) {
        int r1, c1, r2, c2;
        std::cin >> r1 >> c1 >> r2 >> c2;
        std::cout << seg.prod(r1, c1, r2 + 1, c2 + 1) << '\n';
    }
    return;
}

int main() {
    int R, C, Q;
    while (std::cin >> R >> C >> Q, !(R == 0 and C == 0 and Q == 0)) solve(R, C, Q);
    return 0;
}