test/yosupo/staticrmq.sqrt_tree.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 16:48:15+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Sqrt Tree (data-structure/sqrt_tree.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../data-structure/sqrt_tree.hpp"
using namespace std;

struct MinSemigroup {
    using T = int;
    static T op(T a, T b) { return min(a, b); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (auto& x : a) cin >> x;
    SqrtTree<MinSemigroup> st(a);
    while (Q--) {
        int l, r;
        cin >> l >> r;
        cout << st.fold(l, r) << "\n";
    }
}

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

#include <bits/stdc++.h>

#line 3 "data-structure/sqrt_tree.hpp"
#include <bit>
#line 5 "data-structure/sqrt_tree.hpp"

template <typename S>
class SqrtTree {
    using T = S::T;

   public:
    SqrtTree() = default;
    explicit SqrtTree(const std::vector<T>& v) : v(v) {
        const int n = v.size(), lg = std::bit_width((unsigned int)n);
        on_layer.resize(lg + 1);
        int n_layer = 0;
        for (int i = lg; i > 1; i = (i + 1) / 2) {
            on_layer[i] = n_layer++;
            layer_lg.push_back(i);
        }
        for (int i = lg - 1; i >= 0; --i)
            on_layer[i] = std::max(on_layer[i], on_layer[i + 1]);
        pref.resize(n_layer, std::vector<T>(n));
        suf.resize(n_layer, std::vector<T>(n));
        btwn.resize(n_layer, std::vector<T>(1 << lg));

        for (int layer = 0; layer < n_layer; ++layer) {
            int prev_b_sz = 1 << layer_lg[layer];
            int b_sz = 1 << ((layer_lg[layer] + 1) / 2);
            int b_cnt = 1 << (layer_lg[layer] / 2);

            for (int l = 0; l < n; l += prev_b_sz) {
                int r = std::min(l + prev_b_sz, n);

                // calculate pref and suf
                for (int a = l; a < r; a += b_sz) {
                    int b = std::min(a + b_sz, r);
                    pref[layer][a] = v[a];
                    for (int i = a + 1; i < b; ++i) {
                        pref[layer][i] = S::op(pref[layer][i - 1], v[i]);
                    }
                    suf[layer][b - 1] = v[b - 1];
                    for (int i = b - 2; i >= a; --i) {
                        suf[layer][i] = S::op(v[i], suf[layer][i + 1]);
                    }
                }
                // calculate btwn
                for (int i = 0; i < b_cnt; ++i) {
                    T val = suf[layer][l + i * b_sz];
                    btwn[layer][l + i * b_cnt + i] = val;
                    for (int j = i + 1; j < b_cnt; ++j) {
                        val = S::op(val, suf[layer][l + j * b_sz]);
                        btwn[layer][l + i * b_cnt + j] = val;
                    }
                }
            }
        }
    }

    T fold(int l, int r) const {
        --r;
        if (l == r) return v[l];
        if (l + 1 == r) return S::op(v[l], v[r]);
        int layer = on_layer[std::bit_width((unsigned int)(l ^ r))];
        int b_sz = 1 << ((layer_lg[layer] + 1) / 2);
        int b_cnt = 1 << (layer_lg[layer] / 2);
        int a = (l >> layer_lg[layer]) << layer_lg[layer];
        int lblock = (l - a) / b_sz + 1;
        int rblock = (r - a) / b_sz - 1;
        T val = suf[layer][l];
        if (lblock <= rblock)
            val = S::op(val, btwn[layer][a + lblock * b_cnt + rblock]);
        val = S::op(val, pref[layer][r]);
        return val;
    }

   private:
    std::vector<int> layer_lg, on_layer;
    std::vector<T> v;
    std::vector<std::vector<T>> pref, suf, btwn;
};
#line 6 "test/yosupo/staticrmq.sqrt_tree.test.cpp"
using namespace std;

struct MinSemigroup {
    using T = int;
    static T op(T a, T b) { return min(a, b); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (auto& x : a) cin >> x;
    SqrtTree<MinSemigroup> st(a);
    while (Q--) {
        int l, r;
        cin >> l >> r;
        cout << st.fold(l, r) << "\n";
    }
}

Back to top page