Test/yosupo-judge/SparseTable.test.cpp

View this file on GitHub
Last update: 2021-06-18 21:14:35+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

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

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../DataStructure/SparseTable.cpp"

int main() {
    int N,Q;
    cin >> N >> Q;
    vector<int> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    SparseTable st(vec);
    for(int i = 0;i < Q;i++) {
        int l,r;
        cin >> l >> r;
        cout << st.query(l,r) << endl;
    }
}

#line 1 "Test/yosupo-judge/SparseTable.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "DataStructure/SparseTable.cpp"
template <typename T>
class SparseTable {
    vector<vector<T>> table;
    vector<int> lookup;

public:

    SparseTable(vector<T> v) {
        int b = 0;

        while((1 << b) <= v.size()) {
            b++;
        }

        table.resize(b,vector<T>(1 << b));

        for(int i = 0;i < v.size();i++) {
            table[0][i] = v[i];
        }

        for(int i = 1;i < b;i++) {
            for(int j = 0;j + (1 << i) <= (1 << b);j++) {
                table[i][j] = min(table[i - 1][j],table[i - 1][j + (1 << (i - 1))]);
            }
        }

        lookup.resize(v.size() + 1);

        for(int i = 2;i < lookup.size();i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }

    T query(int l,int r) {
        int b = lookup[r - l];
        return min(table[b][l],table[b][r - (1 << b)]);
    }
};
#line 8 "Test/yosupo-judge/SparseTable.test.cpp"

int main() {
    int N,Q;
    cin >> N >> Q;
    vector<int> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    SparseTable st(vec);
    for(int i = 0;i < Q;i++) {
        int l,r;
        cin >> l >> r;
        cout << st.query(l,r) << endl;
    }
}