test/aoj/aoj_1068_1.test.cpp

View this file on GitHub
Last update: 2023-10-31 01:04:45+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 <iostream>
#include <limits>

#include "../../data_structure/segtree.hpp"
#include "../../data_structure/segtree_2d.hpp"

int op(int a, int b) {
    return a < b ? a : b;
}

int e() {
    return std::numeric_limits<int>::max();
}

int main() {
    int r, c, q;
    while (std::cin >> r >> c >> q, !(r == 0 && c == 0 && q == 0)) {
        ebi::segtree_2d<int, op, e, ebi::segtree<int, op, e>> seg2d(r, c);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                int grid;
                std::cin >> grid;
                seg2d.set(i, j, grid);
            }
        }
        while (q--) {
            int l, d, r, u;
            std::cin >> l >> d >> r >> u;
            r++;
            u++;
            std::cout << seg2d.prod(l, d, r, u) << '\n';
        }
    }
}

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

#include <iostream>
#include <limits>

#line 2 "data_structure/segtree.hpp"

#include <cassert>

#include <vector>


namespace ebi {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  private:
    int n;
    int sz;
    std::vector<S> data;

    void update(int i) {
        data[i] = op(data[2 * i], data[2 * i + 1]);
    }

  public:
    segtree(int n_) : segtree(std::vector<S>(n_, e())) {}
    segtree(const std::vector<S> &v) : n((int)v.size()), sz(1) {
        while (sz < n) sz *= 2;
        data = std::vector<S>(2 * sz, e());
        for (int i = 0; i < n; i++) {
            data[sz + i] = v[i];
        }
        for (int i = sz - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += sz;
        data[p] = x;
        while (p > 1) {
            p >>= 1;
            update(p);
        }
    }

    S get(int p) const {
        assert(0 <= p && p < n);
        return data[p + sz];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        S sml = e(), smr = e();
        l += sz;
        r += sz;
        while (l < r) {
            if (l & 1) sml = op(sml, data[l++]);
            if (r & 1) smr = op(data[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

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

    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l < n);
        assert(f(e()));
        if (l == n) return n;
        l += sz;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, data[l]))) {
                while (l < sz) {
                    l = 2 * l;
                    if (f(op(sm, data[l]))) {
                        sm = op(sm, data[l]);
                        l++;
                    }
                }
                return l - sz;
            }
            sm = op(sm, data[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if (r == 0) return 0;
        r += sz;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(data[r], sm))) {
                while (r < sz) {
                    r = 2 * r + 1;
                    if (f(op(data[r], sm))) {
                        sm = op(data[r], sm);
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            sm = op(data[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    S operator[](int p) const {
        return data[sz + p];
    }
};

}  // namespace ebi

#line 2 "data_structure/segtree_2d.hpp"

#line 5 "data_structure/segtree_2d.hpp"

namespace ebi {

template <class S, S (*op)(S, S), S (*e)(), class data_structure>
struct segtree_2d {
  private:
  public:
    segtree_2d(int h, int w) : h(h), w(w), sz(1) {
        while (sz < h) sz <<= 1;
        data = std::vector<data_structure>(2 * sz, data_structure(w));
    }

    void set(int i, int j, S x) {
        assert(0 <= i && i < h && 0 <= j && j < w);
        i += sz;
        data[i].set(j, x);
        while (i > 1) {
            i >>= 1;
            S val = op(data[2 * i].get(j), data[2 * i + 1].get(j));
            data[i].set(j, val);
        }
    }

    S get(int i, int j) const {
        assert(0 <= i && i < h && 0 <= j && j < w);
        return data[i + sz].get(j);
    }

    S prod(int l, int d, int r, int u) const {
        assert(0 <= l && l <= r && r <= h);
        assert(0 <= d && d <= u && u <= w);
        l += sz;
        r += sz;
        S res = e();
        while (l < r) {
            if (l & 1) res = op(res, data[l++].prod(d, u));
            if (r & 1) res = op(data[--r].prod(d, u), res);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

  private:
    int h, w;
    int sz;
    std::vector<data_structure> data;
};

}  // namespace ebi
#line 8 "test/aoj/aoj_1068_1.test.cpp"

int op(int a, int b) {
    return a < b ? a : b;
}

int e() {
    return std::numeric_limits<int>::max();
}

int main() {
    int r, c, q;
    while (std::cin >> r >> c >> q, !(r == 0 && c == 0 && q == 0)) {
        ebi::segtree_2d<int, op, e, ebi::segtree<int, op, e>> seg2d(r, c);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                int grid;
                std::cin >> grid;
                seg2d.set(i, j, grid);
            }
        }
        while (q--) {
            int l, d, r, u;
            std::cin >> l >> d >> r >> u;
            r++;
            u++;
            std::cout << seg2d.prod(l, d, r, u) << '\n';
        }
    }
}