Skip to content

static_range_mode.hpp

SECTIONData Structure INCLUDEnoya/static_range_mode.hpp

预处理静态数组的区间众数查询，返回出现次数最多的值及频次。

Complexity: Time: O(n sqrt(n)) build and O(sqrt(n) log n) query. Space: O(n sqrt(n)).

AC 记录：static_range_mode_query。

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n) log n) query.
/// Space: O(n sqrt(n)).

#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>

namespace noya {

/// @brief Static half-open range mode queries in O(sqrt(n) log n), with
/// O(n sqrt(n)) preprocessing; ties return the smallest value.
template <class T> struct static_range_mode {
  int n = 0;
  int bs = 1;
  int nb = 0;
  std::vector<T> xs;
  std::vector<int> rk;
  std::vector<std::vector<int>> pos;
  std::vector<std::vector<int>> md;

  static_range_mode() = default;
  explicit static_range_mode(const std::vector<T> &a) { build(a); }

  void build(const std::vector<T> &a) {
    n = int(a.size());
    bs = std::max(1, int(std::sqrt(std::max(1, n))));
    nb = (n + bs - 1) / bs;
    xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    rk.resize(n);
    pos.assign(xs.size(), {});
    for (int idx = 0; idx < n; idx++) {
      rk[idx] =
          int(std::lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
      pos[rk[idx]].push_back(idx);
    }
    md.assign(nb, std::vector<int>(nb, -1));
    std::vector<int> cnt(xs.size());
    for (int lb = 0; lb < nb; lb++) {
      std::fill(cnt.begin(), cnt.end(), 0);
      int bst = -1;
      for (int idx = lb * bs; idx < n; idx++) {
        int val = rk[idx];
        cnt[val]++;
        if (bst == -1 || cnt[val] > cnt[bst] ||
            (cnt[val] == cnt[bst] && val < bst)) {
          bst = val;
        }
        int rb = idx / bs;
        md[lb][rb] = bst;
      }
    }
  }

  /// @brief Return (mode, frequency), or nullopt for an empty range.
  std::optional<std::pair<T, int>> query(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) {
      return std::nullopt;
    }
    int fl = (l + bs - 1) / bs;
    int fr = r / bs;
    std::vector<int> cs;
    if (fl < fr) {
      cs.push_back(md[fl][fr - 1]);
    }
    int le = std::min(r, fl * bs);
    for (int idx = l; idx < le; idx++) {
      cs.push_back(rk[idx]);
    }
    int rl = std::max(le, fr * bs);
    for (int idx = rl; idx < r; idx++) {
      cs.push_back(rk[idx]);
    }
    std::sort(cs.begin(), cs.end());
    cs.erase(std::unique(cs.begin(), cs.end()), cs.end());
    int bst = cs[0];
    int bc = -1;
    for (int can : cs) {
      const auto &vec = pos[can];
      int cnt = int(std::lower_bound(vec.begin(), vec.end(), r) -
                    std::lower_bound(vec.begin(), vec.end(), l));
      if (cnt > bc || (cnt == bc && can < bst)) {
        bst = can;
        bc = cnt;
      }
    }
    return std::pair<T, int>{xs[bst], bc};
  }
};

} // namespace noya

#ifndef NOYA_STATIC_RANGE_MODE_HPP
#define NOYA_STATIC_RANGE_MODE_HPP 1

/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n) log n) query.
/// Space: O(n sqrt(n)).

#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>

namespace noya {

/// @brief Static half-open range mode queries in O(sqrt(n) log n), with
/// O(n sqrt(n)) preprocessing; ties return the smallest value.
template <class T> struct static_range_mode {
  int n = 0;
  int bs = 1;
  int nb = 0;
  std::vector<T> xs;
  std::vector<int> rk;
  std::vector<std::vector<int>> pos;
  std::vector<std::vector<int>> md;

  static_range_mode() = default;
  explicit static_range_mode(const std::vector<T> &a) { build(a); }

  void build(const std::vector<T> &a) {
    n = int(a.size());
    bs = std::max(1, int(std::sqrt(std::max(1, n))));
    nb = (n + bs - 1) / bs;
    xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    rk.resize(n);
    pos.assign(xs.size(), {});
    for (int idx = 0; idx < n; idx++) {
      rk[idx] =
          int(std::lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
      pos[rk[idx]].push_back(idx);
    }
    md.assign(nb, std::vector<int>(nb, -1));
    std::vector<int> cnt(xs.size());
    for (int lb = 0; lb < nb; lb++) {
      std::fill(cnt.begin(), cnt.end(), 0);
      int bst = -1;
      for (int idx = lb * bs; idx < n; idx++) {
        int val = rk[idx];
        cnt[val]++;
        if (bst == -1 || cnt[val] > cnt[bst] ||
            (cnt[val] == cnt[bst] && val < bst)) {
          bst = val;
        }
        int rb = idx / bs;
        md[lb][rb] = bst;
      }
    }
  }

  /// @brief Return (mode, frequency), or nullopt for an empty range.
  std::optional<std::pair<T, int>> query(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) {
      return std::nullopt;
    }
    int fl = (l + bs - 1) / bs;
    int fr = r / bs;
    std::vector<int> cs;
    if (fl < fr) {
      cs.push_back(md[fl][fr - 1]);
    }
    int le = std::min(r, fl * bs);
    for (int idx = l; idx < le; idx++) {
      cs.push_back(rk[idx]);
    }
    int rl = std::max(le, fr * bs);
    for (int idx = rl; idx < r; idx++) {
      cs.push_back(rk[idx]);
    }
    std::sort(cs.begin(), cs.end());
    cs.erase(std::unique(cs.begin(), cs.end()), cs.end());
    int bst = cs[0];
    int bc = -1;
    for (int can : cs) {
      const auto &vec = pos[can];
      int cnt = int(std::lower_bound(vec.begin(), vec.end(), r) -
                    std::lower_bound(vec.begin(), vec.end(), l));
      if (cnt > bc || (cnt == bc && can < bst)) {
        bst = can;
        bc = cnt;
      }
    }
    return std::pair<T, int>{xs[bst], bc};
  }
};

} // namespace noya

#endif // NOYA_STATIC_RANGE_MODE_HPP

#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>

/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n) log n) query.
/// Space: O(n sqrt(n)).

namespace noya {

/// @brief Static half-open range mode queries in O(sqrt(n) log n), with
/// O(n sqrt(n)) preprocessing; ties return the smallest value.
template <class T> struct static_range_mode {
  int n = 0;
  int bs = 1;
  int nb = 0;
  std::vector<T> xs;
  std::vector<int> rk;
  std::vector<std::vector<int>> pos;
  std::vector<std::vector<int>> md;

  static_range_mode() = default;
  explicit static_range_mode(const std::vector<T> &a) { build(a); }

  void build(const std::vector<T> &a) {
    n = int(a.size());
    bs = std::max(1, int(std::sqrt(std::max(1, n))));
    nb = (n + bs - 1) / bs;
    xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    rk.resize(n);
    pos.assign(xs.size(), {});
    for (int idx = 0; idx < n; idx++) {
      rk[idx] =
          int(std::lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
      pos[rk[idx]].push_back(idx);
    }
    md.assign(nb, std::vector<int>(nb, -1));
    std::vector<int> cnt(xs.size());
    for (int lb = 0; lb < nb; lb++) {
      std::fill(cnt.begin(), cnt.end(), 0);
      int bst = -1;
      for (int idx = lb * bs; idx < n; idx++) {
        int val = rk[idx];
        cnt[val]++;
        if (bst == -1 || cnt[val] > cnt[bst] ||
            (cnt[val] == cnt[bst] && val < bst)) {
          bst = val;
        }
        int rb = idx / bs;
        md[lb][rb] = bst;
      }
    }
  }

  /// @brief Return (mode, frequency), or nullopt for an empty range.
  std::optional<std::pair<T, int>> query(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) {
      return std::nullopt;
    }
    int fl = (l + bs - 1) / bs;
    int fr = r / bs;
    std::vector<int> cs;
    if (fl < fr) {
      cs.push_back(md[fl][fr - 1]);
    }
    int le = std::min(r, fl * bs);
    for (int idx = l; idx < le; idx++) {
      cs.push_back(rk[idx]);
    }
    int rl = std::max(le, fr * bs);
    for (int idx = rl; idx < r; idx++) {
      cs.push_back(rk[idx]);
    }
    std::sort(cs.begin(), cs.end());
    cs.erase(std::unique(cs.begin(), cs.end()), cs.end());
    int bst = cs[0];
    int bc = -1;
    for (int can : cs) {
      const auto &vec = pos[can];
      int cnt = int(std::lower_bound(vec.begin(), vec.end(), r) -
                    std::lower_bound(vec.begin(), vec.end(), l));
      if (cnt > bc || (cnt == bc && can < bst)) {
        bst = can;
        bc = cnt;
      }
    }
    return std::pair<T, int>{xs[bst], bc};
  }
};

} // namespace noya