dynamic_range_majority.hpp

SECTIONData Structure INCLUDEnoya/dynamic_range_majority.hpp

维护单点修改，并查询区间内是否存在出现次数超过一半的元素及其频次。

Complexity: Time: O((n+u) log(n+u)) preprocessing and O(log n) per update or query. Space: O(n+u), where u is the number of declared updates.

AC 记录：majority_voting。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

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

/// @complexity Time: O((n+u) log(n+u)) preprocessing and O(log n) per update
/// or query.  Space: O(n+u), where u is the number of declared updates.

#include "noya/segtree.hpp"

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

namespace noya {

namespace dynamic_range_majority_detail {

struct vote_monoid {
  using value_type = std::pair<int, int>;
  static value_type unit() { return {0, 0}; }
  static value_type op(value_type l, value_type r) {
    if (l.first == r.first) {
      return {l.first, l.second + r.second};
    }
    if (l.second >= r.second) {
      return {l.first, l.second - r.second};
    }
    return {r.first, r.second - l.second};
  }
};

struct fenwick {
  std::vector<int> dat;

  fenwick() = default;
  explicit fenwick(int sz) : dat(sz + 1) {}

  void add(int pos, int dif) {
    for (pos++; pos < int(dat.size()); pos += pos & -pos) {
      dat[pos] += dif;
    }
  }

  int prefix_sum(int r) const {
    int res = 0;
    for (; r > 0; r -= r & -r) {
      res += dat[r];
    }
    return res;
  }

  int sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l); }
};

} // namespace dynamic_range_majority_detail

/// @brief Point-update range-majority index.  The segment tree applies
/// Boyer--Moore cancellation to obtain the only possible majority, then a
/// coordinate-compressed Fenwick tree for that value certifies its actual
/// frequency.  Every `(pos, future val)` update must be supplied to the
/// constructor so the per-value position lists can be built offline.
template <class T> class dynamic_range_majority {
  using candidate_monoid = dynamic_range_majority_detail::vote_monoid;

  int n = 0;
  std::vector<T> xs_;
  std::vector<int> a;
  std::vector<std::vector<int>> ps;
  std::vector<dynamic_range_majority_detail::fenwick> cnt;
  segtree<candidate_monoid> seg;

  int value_index(const T &val) const {
    auto it = std::lower_bound(xs_.begin(), xs_.end(), val);
    assert(it != xs_.end() && *it == val);
    return int(it - xs_.begin());
  }

  int position_index(int val, int pos) const {
    auto it = std::lower_bound(ps[val].begin(), ps[val].end(), pos);
    assert(it != ps[val].end() && *it == pos);
    return int(it - ps[val].begin());
  }

public:
  dynamic_range_majority() = default;

  dynamic_range_majority(const std::vector<T> &a0,
                         const std::vector<std::pair<int, T>> &upd) {
    build(a0, upd);
  }

  void build(const std::vector<T> &a0,
             const std::vector<std::pair<int, T>> &upd) {
    n = int(a0.size());
    xs_ = a0;
    for (const auto &[pos, val] : upd) {
      assert(0 <= pos && pos < n);
      xs_.push_back(val);
    }
    std::sort(xs_.begin(), xs_.end());
    xs_.erase(std::unique(xs_.begin(), xs_.end()), xs_.end());
    a.resize(n);
    ps.assign(xs_.size(), {});
    for (int pos = 0; pos < n; pos++) {
      a[pos] = value_index(a0[pos]);
      ps[a[pos]].push_back(pos);
    }
    for (const auto &[pos, val] : upd) {
      ps[value_index(val)].push_back(pos);
    }
    cnt.clear();
    cnt.reserve(xs_.size());
    for (auto &vec : ps) {
      std::sort(vec.begin(), vec.end());
      vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
      cnt.emplace_back(int(vec.size()));
    }
    for (int pos = 0; pos < n; pos++) {
      cnt[a[pos]].add(position_index(a[pos], pos), 1);
    }
    seg.build(n, [&](int pos) { return std::pair{a[pos], 1}; });
  }

  int size() const { return n; }

  T get(int pos) const {
    assert(0 <= pos && pos < n);
    return xs_[a[pos]];
  }

  void set(int pos, const T &val) {
    assert(0 <= pos && pos < n);
    int nxt = value_index(val);
    int pre = a[pos];
    if (nxt == pre) {
      return;
    }
    cnt[pre].add(position_index(pre, pos), -1);
    cnt[nxt].add(position_index(nxt, pos), 1);
    a[pos] = nxt;
    seg.set(pos, {nxt, 1});
  }

  std::optional<T> query(int l, int r) const {
    assert(0 <= l && l < r && r <= n);
    int can = seg.prod(l, r).first;
    const auto &vec = ps[can];
    int arr = int(std::lower_bound(vec.begin(), vec.end(), l) - vec.begin());
    int lst = int(std::lower_bound(vec.begin(), vec.end(), r) - vec.begin());
    int num = cnt[can].sum(arr, lst);
    if (num * 2 > r - l) {
      return xs_[can];
    }
    return std::nullopt;
  }
};

} // namespace noya

#ifndef NOYA_DYNAMIC_RANGE_MAJORITY_HPP
#define NOYA_DYNAMIC_RANGE_MAJORITY_HPP 1

/// @complexity Time: O((n+u) log(n+u)) preprocessing and O(log n) per update
/// or query.  Space: O(n+u), where u is the number of declared updates.

#include "noya/segtree.hpp"

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

namespace noya {

namespace dynamic_range_majority_detail {

struct vote_monoid {
  using value_type = std::pair<int, int>;
  static value_type unit() { return {0, 0}; }
  static value_type op(value_type l, value_type r) {
    if (l.first == r.first) {
      return {l.first, l.second + r.second};
    }
    if (l.second >= r.second) {
      return {l.first, l.second - r.second};
    }
    return {r.first, r.second - l.second};
  }
};

struct fenwick {
  std::vector<int> dat;

  fenwick() = default;
  explicit fenwick(int sz) : dat(sz + 1) {}

  void add(int pos, int dif) {
    for (pos++; pos < int(dat.size()); pos += pos & -pos) {
      dat[pos] += dif;
    }
  }

  int prefix_sum(int r) const {
    int res = 0;
    for (; r > 0; r -= r & -r) {
      res += dat[r];
    }
    return res;
  }

  int sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l); }
};

} // namespace dynamic_range_majority_detail

/// @brief Point-update range-majority index.  The segment tree applies
/// Boyer--Moore cancellation to obtain the only possible majority, then a
/// coordinate-compressed Fenwick tree for that value certifies its actual
/// frequency.  Every `(pos, future val)` update must be supplied to the
/// constructor so the per-value position lists can be built offline.
template <class T> class dynamic_range_majority {
  using candidate_monoid = dynamic_range_majority_detail::vote_monoid;

  int n = 0;
  std::vector<T> xs_;
  std::vector<int> a;
  std::vector<std::vector<int>> ps;
  std::vector<dynamic_range_majority_detail::fenwick> cnt;
  segtree<candidate_monoid> seg;

  int value_index(const T &val) const {
    auto it = std::lower_bound(xs_.begin(), xs_.end(), val);
    assert(it != xs_.end() && *it == val);
    return int(it - xs_.begin());
  }

  int position_index(int val, int pos) const {
    auto it = std::lower_bound(ps[val].begin(), ps[val].end(), pos);
    assert(it != ps[val].end() && *it == pos);
    return int(it - ps[val].begin());
  }

public:
  dynamic_range_majority() = default;

  dynamic_range_majority(const std::vector<T> &a0,
                         const std::vector<std::pair<int, T>> &upd) {
    build(a0, upd);
  }

  void build(const std::vector<T> &a0,
             const std::vector<std::pair<int, T>> &upd) {
    n = int(a0.size());
    xs_ = a0;
    for (const auto &[pos, val] : upd) {
      assert(0 <= pos && pos < n);
      xs_.push_back(val);
    }
    std::sort(xs_.begin(), xs_.end());
    xs_.erase(std::unique(xs_.begin(), xs_.end()), xs_.end());
    a.resize(n);
    ps.assign(xs_.size(), {});
    for (int pos = 0; pos < n; pos++) {
      a[pos] = value_index(a0[pos]);
      ps[a[pos]].push_back(pos);
    }
    for (const auto &[pos, val] : upd) {
      ps[value_index(val)].push_back(pos);
    }
    cnt.clear();
    cnt.reserve(xs_.size());
    for (auto &vec : ps) {
      std::sort(vec.begin(), vec.end());
      vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
      cnt.emplace_back(int(vec.size()));
    }
    for (int pos = 0; pos < n; pos++) {
      cnt[a[pos]].add(position_index(a[pos], pos), 1);
    }
    seg.build(n, [&](int pos) { return std::pair{a[pos], 1}; });
  }

  int size() const { return n; }

  T get(int pos) const {
    assert(0 <= pos && pos < n);
    return xs_[a[pos]];
  }

  void set(int pos, const T &val) {
    assert(0 <= pos && pos < n);
    int nxt = value_index(val);
    int pre = a[pos];
    if (nxt == pre) {
      return;
    }
    cnt[pre].add(position_index(pre, pos), -1);
    cnt[nxt].add(position_index(nxt, pos), 1);
    a[pos] = nxt;
    seg.set(pos, {nxt, 1});
  }

  std::optional<T> query(int l, int r) const {
    assert(0 <= l && l < r && r <= n);
    int can = seg.prod(l, r).first;
    const auto &vec = ps[can];
    int arr = int(std::lower_bound(vec.begin(), vec.end(), l) - vec.begin());
    int lst = int(std::lower_bound(vec.begin(), vec.end(), r) - vec.begin());
    int num = cnt[can].sum(arr, lst);
    if (num * 2 > r - l) {
      return xs_[can];
    }
    return std::nullopt;
  }
};

} // namespace noya

#endif // NOYA_DYNAMIC_RANGE_MAJORITY_HPP

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

/// @complexity Time: O((n+u) log(n+u)) preprocessing and O(log n) per update
/// or query.  Space: O(n+u), where u is the number of declared updates.

/// @complexity Time: O(n) build and O(log n) point update/range product.
/// Space: O(n).

namespace noya {

/// @brief Segment tree for a monoid type.
/// Monoid must provide `using value_type`, `value_type unit()`, and
/// `value_type op(value_type, value_type)`.
template <class Monoid> struct segtree {
  using MX = Monoid;
  using S = typename MX::value_type;
  using value_type = S;

  int n = 0;
  int sz = 1;
  std::vector<S> d;

  segtree() : segtree(0) {}
  explicit segtree(int _n) { build(_n); }

  explicit segtree(const std::vector<S> &v) { build(v); }

  template <class F> segtree(int _n, F f) { build(_n, f); }

  void build(int _n) { build(_n, [](int) { return MX::unit(); }); }

  void build(const std::vector<S> &v) {
    build(int(v.size()), [&](int i) { return v[i]; });
  }

  template <class F> void build(int _n, F f) {
    n = _n;
    sz = 1;
    while (sz < n)
      sz <<= 1;
    d.assign(sz << 1, MX::unit());
    for (int i = 0; i < n; i++)
      d[sz + i] = f(i);
    for (int i = sz - 1; i >= 1; i--)
      update(i);
  }

  void set(int p, S x) {
    assert(0 <= p && p < n);
    p += sz;
    d[p] = x;
    while (p >>= 1)
      update(p);
  }

  void multiply(int p, S x) {
    assert(0 <= p && p < n);
    p += sz;
    d[p] = MX::op(d[p], x);
    while (p >>= 1)
      update(p);
  }

  S get(int p) const {
    assert(0 <= p && p < n);
    return d[p + sz];
  }

  std::vector<S> get_all() const {
    return std::vector<S>(d.begin() + sz, d.begin() + sz + n);
  }

  S prod(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    S sml = MX::unit(), smr = MX::unit();
    l += sz;
    r += sz;
    while (l < r) {
      if (l & 1)
        sml = MX::op(sml, d[l++]);
      if (r & 1)
        smr = MX::op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return MX::op(sml, smr);
  }

  S all_prod() const { return d[1]; }

  template <class F> int max_right(int l, F f) const {
    assert(0 <= l && l <= n);
    assert(f(MX::unit()));
    if (l == n)
      return n;
    l += sz;
    S sm = MX::unit();
    do {
      while ((l & 1) == 0)
        l >>= 1;
      if (!f(MX::op(sm, d[l]))) {
        while (l < sz) {
          l <<= 1;
          if (f(MX::op(sm, d[l]))) {
            sm = MX::op(sm, d[l]);
            l++;
          }
        }
        return l - sz;
      }
      sm = MX::op(sm, d[l++]);
    } while ((l & -l) != l);
    return n;
  }

  template <class F> int min_left(int r, F f) const {
    assert(0 <= r && r <= n);
    assert(f(MX::unit()));
    if (r == 0)
      return 0;
    r += sz;
    S sm = MX::unit();
    do {
      --r;
      while (r > 1 && (r & 1))
        r >>= 1;
      if (!f(MX::op(d[r], sm))) {
        while (r < sz) {
          r = (r << 1) | 1;
          if (f(MX::op(d[r], sm))) {
            sm = MX::op(d[r], sm);
            --r;
          }
        }
        return r + 1 - sz;
      }
      sm = MX::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

private:
  void update(int k) { d[k] = MX::op(d[k << 1], d[k << 1 | 1]); }
};

} // namespace noya

namespace noya {

namespace dynamic_range_majority_detail {

struct vote_monoid {
  using value_type = std::pair<int, int>;
  static value_type unit() { return {0, 0}; }
  static value_type op(value_type l, value_type r) {
    if (l.first == r.first) {
      return {l.first, l.second + r.second};
    }
    if (l.second >= r.second) {
      return {l.first, l.second - r.second};
    }
    return {r.first, r.second - l.second};
  }
};

struct fenwick {
  std::vector<int> dat;

  fenwick() = default;
  explicit fenwick(int sz) : dat(sz + 1) {}

  void add(int pos, int dif) {
    for (pos++; pos < int(dat.size()); pos += pos & -pos) {
      dat[pos] += dif;
    }
  }

  int prefix_sum(int r) const {
    int res = 0;
    for (; r > 0; r -= r & -r) {
      res += dat[r];
    }
    return res;
  }

  int sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l); }
};

} // namespace dynamic_range_majority_detail

/// @brief Point-update range-majority index.  The segment tree applies
/// Boyer--Moore cancellation to obtain the only possible majority, then a
/// coordinate-compressed Fenwick tree for that value certifies its actual
/// frequency.  Every `(pos, future val)` update must be supplied to the
/// constructor so the per-value position lists can be built offline.
template <class T> class dynamic_range_majority {
  using candidate_monoid = dynamic_range_majority_detail::vote_monoid;

  int n = 0;
  std::vector<T> xs_;
  std::vector<int> a;
  std::vector<std::vector<int>> ps;
  std::vector<dynamic_range_majority_detail::fenwick> cnt;
  segtree<candidate_monoid> seg;

  int value_index(const T &val) const {
    auto it = std::lower_bound(xs_.begin(), xs_.end(), val);
    assert(it != xs_.end() && *it == val);
    return int(it - xs_.begin());
  }

  int position_index(int val, int pos) const {
    auto it = std::lower_bound(ps[val].begin(), ps[val].end(), pos);
    assert(it != ps[val].end() && *it == pos);
    return int(it - ps[val].begin());
  }

public:
  dynamic_range_majority() = default;

  dynamic_range_majority(const std::vector<T> &a0,
                         const std::vector<std::pair<int, T>> &upd) {
    build(a0, upd);
  }

  void build(const std::vector<T> &a0,
             const std::vector<std::pair<int, T>> &upd) {
    n = int(a0.size());
    xs_ = a0;
    for (const auto &[pos, val] : upd) {
      assert(0 <= pos && pos < n);
      xs_.push_back(val);
    }
    std::sort(xs_.begin(), xs_.end());
    xs_.erase(std::unique(xs_.begin(), xs_.end()), xs_.end());
    a.resize(n);
    ps.assign(xs_.size(), {});
    for (int pos = 0; pos < n; pos++) {
      a[pos] = value_index(a0[pos]);
      ps[a[pos]].push_back(pos);
    }
    for (const auto &[pos, val] : upd) {
      ps[value_index(val)].push_back(pos);
    }
    cnt.clear();
    cnt.reserve(xs_.size());
    for (auto &vec : ps) {
      std::sort(vec.begin(), vec.end());
      vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
      cnt.emplace_back(int(vec.size()));
    }
    for (int pos = 0; pos < n; pos++) {
      cnt[a[pos]].add(position_index(a[pos], pos), 1);
    }
    seg.build(n, [&](int pos) { return std::pair{a[pos], 1}; });
  }

  int size() const { return n; }

  T get(int pos) const {
    assert(0 <= pos && pos < n);
    return xs_[a[pos]];
  }

  void set(int pos, const T &val) {
    assert(0 <= pos && pos < n);
    int nxt = value_index(val);
    int pre = a[pos];
    if (nxt == pre) {
      return;
    }
    cnt[pre].add(position_index(pre, pos), -1);
    cnt[nxt].add(position_index(nxt, pos), 1);
    a[pos] = nxt;
    seg.set(pos, {nxt, 1});
  }

  std::optional<T> query(int l, int r) const {
    assert(0 <= l && l < r && r <= n);
    int can = seg.prod(l, r).first;
    const auto &vec = ps[can];
    int arr = int(std::lower_bound(vec.begin(), vec.end(), l) - vec.begin());
    int lst = int(std::lower_bound(vec.begin(), vec.end(), r) - vec.begin());
    int num = cnt[can].sum(arr, lst);
    if (num * 2 > r - l) {
      return xs_[can];
    }
    return std::nullopt;
  }
};

} // namespace noya