模板 - ST 表

基于 C++14 的 ST 表模板

仅在 GCC 下测试过

成员函数简介

符号说明

  • data_t: 元素类型
  • init_func: 用于初始化的仿函数类型
  • query_func: 用于查询的仿函数类型

简介

成员函数功能
void clear()清空
void init(size_t n)初始化
data_t query(size_t l, size_t r) const查询

代码

Show code

RMQ_ST.hppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <size_t N,
typename data_t,
typename init_func = std::function<data_t(size_t)>,
typename query_func =
std::function<data_t(const data_t &, const data_t &)>>
class RMQ_ST {
protected:
init_func ifunc;
query_func qfunc;
data_t f[(size_t)log2(N) + 1][N];

size_t log_table[N];

public:
RMQ_ST(init_func ifunc, query_func qfunc): ifunc(ifunc), qfunc(qfunc) {}

void clear() { memset(f, 0, sizeof(f)); }

void init(size_t n) {
for (size_t i = 0; i <= n; ++i) f[0][i] = ifunc(i);
for (size_t i = 1; i <= std::log2(n); ++i)
for (size_t j = 0; j + (1 << i) - 1 <= n; ++j)
f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}

data_t query(size_t l, size_t r) const {
size_t _ = std::log2(r - l + 1);
return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
}
};

示例

  • 洛谷 P3865 【模板】ST 表

    Show code

    Luogu_P3865view raw
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    /*
    * @Author: Tifa
    * @Description: From <https://github.com/Tiphereth-A/CP-archives>
    * !!! ATTENEION: All the context below is licensed under a
    * GNU Affero General Public License, Version 3.
    * See <https://www.gnu.org/licenses/agpl-3.0.txt>.
    */
    #include <bits/stdc++.h>
    using namespace std;
    #define _for(i, l, r, vals...) \
    for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
    const uint32_t OFFSET = 5;
    const uint32_t N = 1e5 + OFFSET, M = 5e5 + OFFSET, K = 21;
    int a[N];
    template <size_t N, typename data_t, typename init_func, typename query_func>
    class RMQ_ST {
    protected:
    init_func ifunc;
    query_func qfunc;
    data_t f[(size_t)log2(N) + 1][N];
    size_t log_table[N];

    public:
    RMQ_ST() {}
    void clear() { memset(f, 0, sizeof(f)); }
    void init(size_t n) {
    for (size_t i = 1; i <= n; ++i) f[0][i] = ifunc(i);
    for (size_t i = 1; i <= std::log2(n); ++i)
    for (size_t j = 1; j + (1 << i) - 1 <= n; ++j)
    f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    data_t query(size_t l, size_t r) const {
    size_t _ = std::log2(r - l + 1);
    return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
    }
    };
    struct ifunc {
    int operator()(const size_t x) const { return a[x]; }
    };
    struct qfunc {
    int operator()(const int l, const int r) const { return std::max(l, r); }
    };
    RMQ_ST<N, int, ifunc, qfunc> st;
    auto solve() -> void {
    int n, m;
    cin >> n >> m;
    _for(i, 1, n) cin >> a[i];
    st.init(n);
    _for(i, 1, m, x, y) {
    cin >> x >> y;
    cout << st.query(x, y) << '\n';
    }
    }
    int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
    }
  • Codeforces 522D Closest Equals

    Show code

    CodeForces_522Dview raw
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    /*
    * @Author: Tifa
    * @Description: From <https://github.com/Tiphereth-A/CP-archives>
    * !!! ATTENEION: All the context below is licensed under a
    * GNU Affero General Public License, Version 3.
    * See <https://www.gnu.org/licenses/agpl-3.0.txt>.
    */
    #include <bits/stdc++.h>
    using namespace std;
    #define _for(i, l, r, vals...) \
    for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
    const uint32_t OFFSET = 5;
    const uint32_t N = 5e5 + OFFSET, M = 5e5 + OFFSET, K = 21;
    map<int, int> idx;
    int pos[N];
    struct Seq {
    int l, r;
    } s[N];
    int cnt_s;
    template <size_t N, typename data_t, typename init_func, typename query_func>
    class RMQ_ST {
    protected:
    init_func ifunc;
    query_func qfunc;
    data_t f[(size_t)log2(N) + 1][N];
    size_t log_table[N];

    public:
    RMQ_ST() {}
    void clear() { memset(f, 0, sizeof(f)); }
    void init(size_t n) {
    for (size_t i = 1; i <= n; ++i) f[0][i] = ifunc(i);
    for (size_t i = 1; i <= std::log2(n); ++i)
    for (size_t j = 1; j + (1 << i) - 1 <= n; ++j)
    f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    data_t query(size_t l, size_t r) const {
    size_t _ = std::log2(r - l + 1);
    return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
    }
    };
    struct ifunc {
    int operator()(const size_t n) const { return s[n].r - s[n].l; }
    };
    struct qfunc {
    int operator()(const int l, const int r) const { return std::min(l, r); }
    };
    RMQ_ST<N, int, ifunc, qfunc> st;
    auto solve() -> void {
    int n, m;
    cin >> n >> m;
    _for(i, 1, n, x, pre) {
    cin >> x;
    if ((pre = idx[x]) && (pre > s[cnt_s].l)) s[++cnt_s] = {pre, i};
    idx[x] = i;
    }
    st.init(cnt_s);
    _for(i, 1, m, x, y, l, r) {
    cin >> x >> y;
    l = lower_bound(s + 1,
    s + cnt_s + 1,
    x,
    [](const Seq &it, int v) -> bool { return it.l < v; }) -
    s;
    r = upper_bound(s + 1,
    s + cnt_s + 1,
    y,
    [](int v, const Seq &it) -> bool { return it.r > v; }) -
    s - 1;
    cout << (l <= r ? st.query(l, r) : -1) << '\n';
    }
    }
    int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
    }
  • Codeforces 1691D Max GEQ Sum

    Show code

    CodeForces_1691Dview raw
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    /*
    * @Author: Tifa
    * @Description: From <https://github.com/Tiphereth-A/CP-archives>
    * !!! ATTENEION: All the context below is licensed under a
    * GNU Affero General Public License, Version 3.
    * See <https://www.gnu.org/licenses/agpl-3.0.txt>.
    */
    #include <bits/stdc++.h>
    using namespace std;
    using i64 = int64_t;
    #define _for(i, l, r, vals...) \
    for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
    template <class T>
    bool chkmin(T &a, T b) {
    return b < a ? a = b, true : false;
    }
    template <class T>
    bool chkmax(T &a, T b) {
    return a < b ? a = b, true : false;
    }
    const uint32_t OFFSET = 5;
    const uint32_t N = 2e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
    template <size_t N,
    typename data_t,
    typename init_func = std::function<data_t(size_t)>,
    typename query_func =
    std::function<data_t(const data_t &, const data_t &)>>
    class RMQ_ST {
    protected:
    init_func ifunc;
    query_func qfunc;
    data_t f[(size_t)log2(N) + 1][N];
    size_t log_table[N];

    public:
    RMQ_ST(init_func ifunc, query_func qfunc): ifunc(ifunc), qfunc(qfunc) {}
    void init(size_t n) {
    for (size_t i = 0; i <= n; ++i) f[0][i] = ifunc(i);
    for (size_t i = 1; i <= std::log2(n); ++i)
    for (size_t j = 0; j + (1 << i) - 1 <= n; ++j)
    f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    data_t query(size_t l, size_t r) const {
    size_t _ = std::log2(r - l + 1);
    return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
    }
    };
    int a[N];
    i64 sum[N];
    RMQ_ST<N, int> max_a([](const size_t i) { return i; },
    [](const int l, const int r) {
    return a[l] < a[r] ? r : l;
    });
    RMQ_ST<N, i64> min_sum([](const size_t i) { return sum[i]; },
    [](const i64 l, const i64 r) { return min(l, r); });
    RMQ_ST<N, i64> max_sum([](const size_t i) { return sum[i]; },
    [](const i64 l, const i64 r) { return max(l, r); });
    bool dfs(int l, int r) {
    if (l >= r) return true;
    int now = max_a.query(l, r);
    i64 mins = min_sum.query(l - 1, now - 1), maxs = max_sum.query(now, r);
    if (a[now] < maxs - mins) return false;
    return dfs(l, now - 1) && dfs(now + 1, r);
    }
    auto solve() -> void {
    int n;
    cin >> n;
    _for(i, 1, n) cin >> a[i];
    _for(i, 1, n) sum[i] = sum[i - 1] + a[i];
    max_a.init(n);
    max_sum.init(n);
    min_sum.init(n);
    cout << (dfs(1, n) ? "YES\n" : "NO\n");
    }
    int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _t;
    cin >> _t;
    while (_t--) solve();
    return 0;
    }