dynamic_range_majority.hpp

SECTIONData Structure INCLUDEnoya/dynamic_range_majority.hpp

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 (position, future value) update must be supplied to the constructor so the per-value position lists can be built offline.

Verified by majority_voting.

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

Implementation

View on GitHub

SourceExpanded

#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 left, value_type right) {
    if (left.first == right.first) {
      return {left.first, left.second + right.second};
    }
    if (left.second >= right.second) {
      return {left.first, left.second - right.second};
    }
    return {right.first, right.second - left.second};
  }
};

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

  fenwick() = default;
  explicit fenwick(int size) : data(size + 1) {}

  void add(int position, int delta) {
    for (position++; position < int(data.size());
         position += position & -position) {
      data[position] += delta;
    }
  }

  int prefix_sum(int right) const {
    int result = 0;
    for (; right > 0; right -= right & -right) {
      result += data[right];
    }
    return result;
  }

  int sum(int left, int right) const {
    return prefix_sum(right) - prefix_sum(left);
  }
};

} // 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 `(position, future value)` 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 size_ = 0;
  std::vector<T> coordinates_;
  std::vector<int> values_;
  std::vector<std::vector<int>> positions_;
  std::vector<dynamic_range_majority_detail::fenwick> occurrences_;
  segtree<candidate_monoid> candidates_;

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

  int position_index(int value, int position) const {
    auto iterator = std::lower_bound(positions_[value].begin(),
                                     positions_[value].end(), position);
    assert(iterator != positions_[value].end() && *iterator == position);
    return int(iterator - positions_[value].begin());
  }

public:
  dynamic_range_majority() = default;

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

  void build(const std::vector<T> &initial,
             const std::vector<std::pair<int, T>> &possible_updates) {
    size_ = int(initial.size());
    coordinates_ = initial;
    for (const auto &[position, value] : possible_updates) {
      assert(0 <= position && position < size_);
      coordinates_.push_back(value);
    }
    std::sort(coordinates_.begin(), coordinates_.end());
    coordinates_.erase(
        std::unique(coordinates_.begin(), coordinates_.end()),
        coordinates_.end());
    values_.resize(size_);
    positions_.assign(coordinates_.size(), {});
    for (int position = 0; position < size_; position++) {
      values_[position] = value_index(initial[position]);
      positions_[values_[position]].push_back(position);
    }
    for (const auto &[position, value] : possible_updates) {
      positions_[value_index(value)].push_back(position);
    }
    occurrences_.clear();
    occurrences_.reserve(coordinates_.size());
    for (auto &positions : positions_) {
      std::sort(positions.begin(), positions.end());
      positions.erase(std::unique(positions.begin(), positions.end()),
                      positions.end());
      occurrences_.emplace_back(int(positions.size()));
    }
    for (int position = 0; position < size_; position++) {
      occurrences_[values_[position]].add(
          position_index(values_[position], position), 1);
    }
    candidates_.build(size_,
                      [&](int position) {
                        return std::pair{values_[position], 1};
                      });
  }

  int size() const { return size_; }

  T get(int position) const {
    assert(0 <= position && position < size_);
    return coordinates_[values_[position]];
  }

  void set(int position, const T &value) {
    assert(0 <= position && position < size_);
    int next = value_index(value);
    int previous = values_[position];
    if (next == previous) {
      return;
    }
    occurrences_[previous].add(position_index(previous, position), -1);
    occurrences_[next].add(position_index(next, position), 1);
    values_[position] = next;
    candidates_.set(position, {next, 1});
  }

  std::optional<T> query(int left, int right) const {
    assert(0 <= left && left < right && right <= size_);
    int candidate = candidates_.prod(left, right).first;
    const auto &positions = positions_[candidate];
    int first = int(std::lower_bound(positions.begin(), positions.end(), left) -
                    positions.begin());
    int last = int(std::lower_bound(positions.begin(), positions.end(), right) -
                   positions.begin());
    int count = occurrences_[candidate].sum(first, last);
    if (count * 2 > right - left) {
      return coordinates_[candidate];
    }
    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 size = 1;
  std::vector<S> d;

  segtree() {}
  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;
    size = 1;
    while (size < n)
      size <<= 1;
    d.assign(size << 1, MX::unit());
    for (int i = 0; i < n; i++)
      d[size + i] = f(i);
    for (int i = size - 1; i >= 1; i--)
      update(i);
  }

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

  void multiply(int p, S x) {
    assert(0 <= p && p < n);
    p += size;
    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 + size];
  }

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

  S prod(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    S sml = MX::unit(), smr = MX::unit();
    l += size;
    r += size;
    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 += size;
    S sm = MX::unit();
    do {
      while ((l & 1) == 0)
        l >>= 1;
      if (!f(MX::op(sm, d[l]))) {
        while (l < size) {
          l <<= 1;
          if (f(MX::op(sm, d[l]))) {
            sm = MX::op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      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 += size;
    S sm = MX::unit();
    do {
      --r;
      while (r > 1 && (r & 1))
        r >>= 1;
      if (!f(MX::op(d[r], sm))) {
        while (r < size) {
          r = (r << 1) | 1;
          if (f(MX::op(d[r], sm))) {
            sm = MX::op(d[r], sm);
            --r;
          }
        }
        return r + 1 - size;
      }
      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 left, value_type right) {
    if (left.first == right.first) {
      return {left.first, left.second + right.second};
    }
    if (left.second >= right.second) {
      return {left.first, left.second - right.second};
    }
    return {right.first, right.second - left.second};
  }
};

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

  fenwick() = default;
  explicit fenwick(int size) : data(size + 1) {}

  void add(int position, int delta) {
    for (position++; position < int(data.size());
         position += position & -position) {
      data[position] += delta;
    }
  }

  int prefix_sum(int right) const {
    int result = 0;
    for (; right > 0; right -= right & -right) {
      result += data[right];
    }
    return result;
  }

  int sum(int left, int right) const {
    return prefix_sum(right) - prefix_sum(left);
  }
};

} // 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 `(position, future value)` 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 size_ = 0;
  std::vector<T> coordinates_;
  std::vector<int> values_;
  std::vector<std::vector<int>> positions_;
  std::vector<dynamic_range_majority_detail::fenwick> occurrences_;
  segtree<candidate_monoid> candidates_;

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

  int position_index(int value, int position) const {
    auto iterator = std::lower_bound(positions_[value].begin(),
                                     positions_[value].end(), position);
    assert(iterator != positions_[value].end() && *iterator == position);
    return int(iterator - positions_[value].begin());
  }

public:
  dynamic_range_majority() = default;

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

  void build(const std::vector<T> &initial,
             const std::vector<std::pair<int, T>> &possible_updates) {
    size_ = int(initial.size());
    coordinates_ = initial;
    for (const auto &[position, value] : possible_updates) {
      assert(0 <= position && position < size_);
      coordinates_.push_back(value);
    }
    std::sort(coordinates_.begin(), coordinates_.end());
    coordinates_.erase(
        std::unique(coordinates_.begin(), coordinates_.end()),
        coordinates_.end());
    values_.resize(size_);
    positions_.assign(coordinates_.size(), {});
    for (int position = 0; position < size_; position++) {
      values_[position] = value_index(initial[position]);
      positions_[values_[position]].push_back(position);
    }
    for (const auto &[position, value] : possible_updates) {
      positions_[value_index(value)].push_back(position);
    }
    occurrences_.clear();
    occurrences_.reserve(coordinates_.size());
    for (auto &positions : positions_) {
      std::sort(positions.begin(), positions.end());
      positions.erase(std::unique(positions.begin(), positions.end()),
                      positions.end());
      occurrences_.emplace_back(int(positions.size()));
    }
    for (int position = 0; position < size_; position++) {
      occurrences_[values_[position]].add(
          position_index(values_[position], position), 1);
    }
    candidates_.build(size_,
                      [&](int position) {
                        return std::pair{values_[position], 1};
                      });
  }

  int size() const { return size_; }

  T get(int position) const {
    assert(0 <= position && position < size_);
    return coordinates_[values_[position]];
  }

  void set(int position, const T &value) {
    assert(0 <= position && position < size_);
    int next = value_index(value);
    int previous = values_[position];
    if (next == previous) {
      return;
    }
    occurrences_[previous].add(position_index(previous, position), -1);
    occurrences_[next].add(position_index(next, position), 1);
    values_[position] = next;
    candidates_.set(position, {next, 1});
  }

  std::optional<T> query(int left, int right) const {
    assert(0 <= left && left < right && right <= size_);
    int candidate = candidates_.prod(left, right).first;
    const auto &positions = positions_[candidate];
    int first = int(std::lower_bound(positions.begin(), positions.end(), left) -
                    positions.begin());
    int last = int(std::lower_bound(positions.begin(), positions.end(), right) -
                   positions.begin());
    int count = occurrences_[candidate].sum(first, last);
    if (count * 2 > right - left) {
      return coordinates_[candidate];
    }
    return std::nullopt;
  }
};

} // namespace noya