test/data_structure/Static_Rmq.test.cpp

• View this file on GitHub
• Last update: 2023-07-17 14:12:40+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Sparse Table (data_structure/sparse_table.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <iostream>

#include <vector>


#include "../../data_structure/sparse_table.hpp"


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

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    ebi::sparse_table<int, op> st(a);
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << st.fold(l, r) << std::endl;
    }
}

#line 1 "test/data_structure/Static_Rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <iostream>

#include <vector>


#line 2 "data_structure/sparse_table.hpp"

#line 4 "data_structure/sparse_table.hpp"

/*
    reference: https://scrapbox.io/data-structures/Sparse_Table
*/

namespace ebi {

template <class Band, Band (*op)(Band, Band)> struct sparse_table {
  public:
    sparse_table() = default;

    sparse_table(const std::vector<Band> &a) : n(a.size()) {
        table = std::vector(std::__lg(n) + 1, std::vector<Band>(n));
        for (int i = 0; i < n; i++) {
            table[0][i] = a[i];
        }
        for (int k = 1; (1 << k) <= n; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                table[k][i] =
                    op(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    void build(const std::vector<Band> &a) {
        n = (int)a.size();
        table = std::vector(std::__lg(n) + 1, std::vector<Band>(n));
        for (int i = 0; i < n; i++) {
            table[0][i] = a[i];
        }
        for (int k = 1; (1 << k) <= n; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                table[k][i] =
                    op(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // [l, r)

    Band fold(int l, int r) {
        int k = std::__lg(r - l);
        return op(table[k][l], table[k][r - (1 << k)]);
    }

  private:
    int n;
    std::vector<std::vector<Band>> table;
};

}  // namespace ebi
#line 7 "test/data_structure/Static_Rmq.test.cpp"

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

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    ebi::sparse_table<int, op> st(a);
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << st.fold(l, r) << std::endl;
    }
}

Back to top page