模板 - ST 表

发表于 更新于 分类于 ， 本文字数： 218 阅读时长 ≈ 1 分钟

基于 C++14 的 ST 表模板

仅在 GCC 下测试过

https://cplib.tifa-233.com/src/code/ds/st_array.hpp 存放了笔者对该算法 / 数据结构的最新实现，建议前往此处查看相关代码

成员函数简介

符号说明

  • 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;
    }