datastructure/plus_minus_one_range_minimum.hpp

• View this file on GitHub
• Last update: 2022-09-01 13:39:43+09:00
• Include: #include "datastructure/plus_minus_one_range_minimum.hpp"

Depends on

• datastructure/static_range_minimum.hpp

Required by

• 最小共通祖先(LCA) (graph/lowest_common_ancestor.hpp)

Verified with

• test/library-checker/lca.test.cpp

Code

#pragma once
#include <cmath>
#include <vector>

#include "static_range_minimum.hpp"
struct PlusMinusOneRMQ {
public:
    void init(const std::vector<int>& _v) {
        _n = int(_v.size());
        v = _v;
        s = std::max(1, int(std::log2(_n) / 2));
        B = (_n + s - 1) / s;
        std::vector<std::pair<int, int>> _spt(B);
        pattern.resize(B);
        for (int i = 0; i < _n; i += s) {
            int min_j = i;
            int bit = 0;
            for (int j = i; j < std::min(_n, i + s); j++) {
                if (v[j] < v[min_j]) min_j = j;
                if (j + 1 < std::min(_n, i + s) && v[j] < v[j + 1])
                    bit |= 1 << (j - i);
            }
            _spt[i / s] = {v[min_j], min_j};
            pattern[i / s] = bit;
        }
        sparse_table.init(_spt);

        lookup_table.resize(1 << (s - 1));
        for (int bit = 0; bit < (1 << (s - 1)); bit++) {
            lookup_table[bit].resize(s + 1);
            for (int l = 0; l <= s; l++) {
                lookup_table[bit][l].resize(s + 1, INF);
                int min_ = 0;
                int min_i = l;
                int sum = 0;
                for (int r = l + 1; r <= s; r++) {
                    lookup_table[bit][l][r] = min_i;
                    sum += bit >> (r - 1) & 1 ? 1 : -1;
                    if (sum < min_) {
                        min_ = sum;
                        min_i = r;
                    }
                }
            }
        }
    }
    int prod(int l, int r) {
        int m1 = (l + s - 1) / s;
        int m2 = r / s;
        int l1 = s * m1;
        int r1 = s * m2;
        if (m2 < m1) {
            return lookup_table[pattern[m2]][l - r1][r - r1] + r1;
        }
        int ret = INF;
        if (m1 > 0) {
            ret = argmin(
                ret, lookup_table[pattern[m1 - 1]][s - (l1 - l)][s] + l1 - s);
        }
        ret = argmin(ret, sparse_table.prod(m1, m2).second);
        if (m2 < B) {
            ret = argmin(ret, lookup_table[pattern[m2]][0][r - r1] + r1);
        }
        return ret;
    }

private:
    int _n;
    int s, B;
    StaticRMQ sparse_table;
    std::vector<std::vector<std::vector<int>>> lookup_table;
    std::vector<int> pattern, v;
    const int INF = 1 << 30;
    int argmin(int i, int j) {
        if (i >= INF || j >= INF || v[i] == v[j]) return std::min(i, j);
        return v[i] < v[j] ? i : j;
    }
};

#line 2 "datastructure/plus_minus_one_range_minimum.hpp"
#include <cmath>
#include <vector>

#line 3 "datastructure/static_range_minimum.hpp"
struct StaticRMQ {
public:
    void init(const std::vector<std::pair<int, int>>& _v) {
        _n = int(_v.size()), d.resize(_n), ceil_log2.resize(_n + 1);
        ceil_log2[0] = 0;
        ceil_log2[1] = 0;
        for (int i = 2; i <= _n; i++) ceil_log2[i] = ceil_log2[i >> 1] + 1;
        for (int i = 0; i < _n; i++) {
            d[i].resize(ceil_log2[_n] + 1);
            d[i][0] = _v[i];
        }
        for (int b = 0; b < ceil_log2[_n]; b++) {
            for (int i = 0; i < _n; i++) {
                if (i + (1 << (b + 1)) > _n) break;
                d[i][b + 1] = std::min(d[i][b], d[i + (1 << b)][b]);
            }
        }
    }
    std::pair<int, int> prod(int l, int r) {
        if (!(l < r)) return PINF;
        int b = ceil_log2[r - l];
        return std::min(d[l][b], d[r - (1 << b)][b]);
    }

private:
    int _n;
    std::vector<std::vector<std::pair<int, int>>> d;
    std::vector<int> ceil_log2;
    const std::pair<int, int> PINF = {1 << 30, 1 << 30};
};
#line 6 "datastructure/plus_minus_one_range_minimum.hpp"
struct PlusMinusOneRMQ {
public:
    void init(const std::vector<int>& _v) {
        _n = int(_v.size());
        v = _v;
        s = std::max(1, int(std::log2(_n) / 2));
        B = (_n + s - 1) / s;
        std::vector<std::pair<int, int>> _spt(B);
        pattern.resize(B);
        for (int i = 0; i < _n; i += s) {
            int min_j = i;
            int bit = 0;
            for (int j = i; j < std::min(_n, i + s); j++) {
                if (v[j] < v[min_j]) min_j = j;
                if (j + 1 < std::min(_n, i + s) && v[j] < v[j + 1])
                    bit |= 1 << (j - i);
            }
            _spt[i / s] = {v[min_j], min_j};
            pattern[i / s] = bit;
        }
        sparse_table.init(_spt);

        lookup_table.resize(1 << (s - 1));
        for (int bit = 0; bit < (1 << (s - 1)); bit++) {
            lookup_table[bit].resize(s + 1);
            for (int l = 0; l <= s; l++) {
                lookup_table[bit][l].resize(s + 1, INF);
                int min_ = 0;
                int min_i = l;
                int sum = 0;
                for (int r = l + 1; r <= s; r++) {
                    lookup_table[bit][l][r] = min_i;
                    sum += bit >> (r - 1) & 1 ? 1 : -1;
                    if (sum < min_) {
                        min_ = sum;
                        min_i = r;
                    }
                }
            }
        }
    }
    int prod(int l, int r) {
        int m1 = (l + s - 1) / s;
        int m2 = r / s;
        int l1 = s * m1;
        int r1 = s * m2;
        if (m2 < m1) {
            return lookup_table[pattern[m2]][l - r1][r - r1] + r1;
        }
        int ret = INF;
        if (m1 > 0) {
            ret = argmin(
                ret, lookup_table[pattern[m1 - 1]][s - (l1 - l)][s] + l1 - s);
        }
        ret = argmin(ret, sparse_table.prod(m1, m2).second);
        if (m2 < B) {
            ret = argmin(ret, lookup_table[pattern[m2]][0][r - r1] + r1);
        }
        return ret;
    }

private:
    int _n;
    int s, B;
    StaticRMQ sparse_table;
    std::vector<std::vector<std::vector<int>>> lookup_table;
    std::vector<int> pattern, v;
    const int INF = 1 << 30;
    int argmin(int i, int j) {
        if (i >= INF || j >= INF || v[i] == v[j]) return std::min(i, j);
        return v[i] < v[j] ? i : j;
    }
};

Back to top page