rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: segment_tree/test/segment_tree_2d.test.cpp

Depends on

Code

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

#include <iostream>
#include <limits>

#include "../../algebra/monoid/monoid_min.hpp"
#include "../../segment_tree/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];
        }
    }
    constexpr int INF = std::numeric_limits<int>::max();
    SegmentTree2D<MonoidMin<int, INF>> 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 "segment_tree/test/segment_tree_2d.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1068"

#include <iostream>
#include <limits>

#line 2 "algebra/monoid/monoid_min.hpp"

template <class T, T inf> struct MonoidMin {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return std::min(a, b);
    }
    static constexpr T identity() noexcept { return inf; }
    static constexpr bool commutative = true;
};
#line 2 "segment_tree/segment_tree_2d.hpp"

#line 2 "misc/bit_ceil.hpp"

#include <cassert>

#if __cplusplus >= 202002L
#include <bit>
#endif

// bit_ceil
// (0, 1, 2, 3, 4) -> (1, 1, 2, 4, 4)
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int x) {
    unsigned int p = 1;
    while (p < x) p *= 2;
    return p;
}
unsigned long long int bit_ceil(unsigned long long int x) {
    unsigned long long int p = 1;
    while (p < x) p *= 2;
    return p;
}
#endif
int bit_ceil(int x) {
    assert(x >= 0);
    return bit_ceil((unsigned int)(x));
}
long long int bit_ceil(long long int x) {
    assert(x >= 0);
    return bit_ceil((unsigned long long int)(x));
}
#line 2 "misc/countr_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countr_zero
// (000, 001, 010, 011, 100) -> (32, 0, 1, 0, 2)
#if __cplusplus >= 202002L
using std::countr_zero;
#else
int countr_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_ctz(x);
}
int countr_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_ctzll(x);
}
#endif
int countr_zero(int x) { return countr_zero((unsigned int)(x)); }
int countr_zero(long long int x) {
    return countr_zero((unsigned long long int)(x));
}
#line 5 "segment_tree/segment_tree_2d.hpp"

#line 7 "segment_tree/segment_tree_2d.hpp"
#include <vector>

// Segment Tree 2D
template <class MS> struct SegmentTree2D {
  public:
    using S = typename MS::value_type;

    SegmentTree2D() = default;

    explicit SegmentTree2D(int h, int w)
        : SegmentTree2D(std::vector(h, std::vector<S>(w, MS::identity()))) {}

    explicit SegmentTree2D(const std::vector<std::vector<S>>& v)
        : h((int)(v.size())), w((int)(v[0].size())) {
        sizeh = bit_ceil(h);
        logh = countr_zero(sizeh);
        sizew = bit_ceil(w);
        logw = countr_zero(sizew);
        d = std::vector(sizeh << 1, std::vector<S>(sizew << 1, MS::identity()));
        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 add(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::operation(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::identity(), smr = MS::identity();
        while (w1 < w2) {
            if (w1 & 1) sml = MS::operation(sml, d[h][w1++]);
            if (w2 & 1) smr = MS::operation(d[h][--w2], smr);
            w1 >>= 1;
            w2 >>= 1;
        }
        return MS::operation(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::identity(), smr = MS::identity();
        h1 += sizeh;
        h2 += sizeh;
        w1 += sizew;
        w2 += sizew;

        while (h1 < h2) {
            if (h1 & 1) sml = MS::operation(sml, inner_prod(h1++, w1, w2));
            if (h2 & 1) smr = MS::operation(inner_prod(--h2, w1, w2), smr);
            h1 >>= 1;
            h2 >>= 1;
        }
        return MS::operation(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::operation(d[(i << 1) | 0][j], d[(i << 1) | 1][j]);
    }

    inline void update_else(int i, int j) {
        d[i][j] = MS::operation(d[i][(j << 1) | 0], d[i][(j << 1) | 1]);
    }
};
#line 8 "segment_tree/test/segment_tree_2d.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];
        }
    }
    constexpr int INF = std::numeric_limits<int>::max();
    SegmentTree2D<MonoidMin<int, INF>> 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;
}
Back to top page