consecutive_segment.hpp

SECTIONData Structure INCLUDEnoya/consecutive_segment.hpp

维护定义在 \([0,N)\) 上的分段常值序列，支持单点取值、覆盖 \([l,r)\)，并返回覆盖前的各个分段；适合 ODT 式区间赋值及按旧段增删贡献。

\[ \displaystyle \operatorname{get}(x)=A_x,\qquad \operatorname{assign}(l,r,v):\ A_i\leftarrow v\quad(l\le i<r) \]

Complexity: Time: O(log K) for get and O(log K + s) for assign, where K is the number of stored segments and s is the number of overwritten segments. Space: O(K).

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

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

/// @complexity Time: O(log K) for get and O(log K + s) for assign, where K is
/// the number of stored segments and s is the number of overwritten segments.
/// Space: O(K).

#include <iterator>
#include <map>
#include <tuple>
#include <vector>

namespace noya {

/// @brief Maintain a piecewise-constant sequence under interval assignment and
/// return the overwritten segments.
template <class T> struct consecutive_segment {
  std::map<int, T> mp;
  consecutive_segment() {}
  consecutive_segment(int N, int v = 0) { mp[N] = v; }
  void split(int x) {
    auto it = mp.lower_bound(x);
    mp[x] = it->second;
  }

  /// @brief Get the value at position x.
  T get(int x) const {
    return mp.upper_bound(x)->second;
  }

  /// @brief Assign [l, r) = v.
  /// @return The original segments as vector of (left, right, value).
  std::vector<std::tuple<int, int, T>> assign(int l, int r, T v) {
    if (l == r)
      return {};
    split(l);
    split(r);
    auto it = mp.find(l);
    T t = mp[l];
    std::vector<std::tuple<int, int, T>> seg;
    while (it->first != r) {
      auto nx = next(it);
      seg.push_back({it->first, nx->first, nx->second});
      it = mp.erase(it);
    }
    mp[l] = t;
    mp[r] = v;
    return seg;
  }
};

} // namespace noya

#ifndef NOYA_CONSECUTIVE_SEGMENT_HPP
#define NOYA_CONSECUTIVE_SEGMENT_HPP 1

/// @complexity Time: O(log K) for get and O(log K + s) for assign, where K is
/// the number of stored segments and s is the number of overwritten segments.
/// Space: O(K).

#include <iterator>
#include <map>
#include <tuple>
#include <vector>

namespace noya {

/// @brief Maintain a piecewise-constant sequence under interval assignment and
/// return the overwritten segments.
template <class T> struct consecutive_segment {
  std::map<int, T> mp;
  consecutive_segment() {}
  consecutive_segment(int N, int v = 0) { mp[N] = v; }
  void split(int x) {
    auto it = mp.lower_bound(x);
    mp[x] = it->second;
  }

  /// @brief Get the value at position x.
  T get(int x) const {
    return mp.upper_bound(x)->second;
  }

  /// @brief Assign [l, r) = v.
  /// @return The original segments as vector of (left, right, value).
  std::vector<std::tuple<int, int, T>> assign(int l, int r, T v) {
    if (l == r)
      return {};
    split(l);
    split(r);
    auto it = mp.find(l);
    T t = mp[l];
    std::vector<std::tuple<int, int, T>> seg;
    while (it->first != r) {
      auto nx = next(it);
      seg.push_back({it->first, nx->first, nx->second});
      it = mp.erase(it);
    }
    mp[l] = t;
    mp[r] = v;
    return seg;
  }
};

} // namespace noya

#endif // NOYA_CONSECUTIVE_SEGMENT_HPP

#include <iterator>
#include <map>
#include <tuple>
#include <vector>

/// @complexity Time: O(log K) for get and O(log K + s) for assign, where K is
/// the number of stored segments and s is the number of overwritten segments.
/// Space: O(K).

namespace noya {

/// @brief Maintain a piecewise-constant sequence under interval assignment and
/// return the overwritten segments.
template <class T> struct consecutive_segment {
  std::map<int, T> mp;
  consecutive_segment() {}
  consecutive_segment(int N, int v = 0) { mp[N] = v; }
  void split(int x) {
    auto it = mp.lower_bound(x);
    mp[x] = it->second;
  }

  /// @brief Get the value at position x.
  T get(int x) const {
    return mp.upper_bound(x)->second;
  }

  /// @brief Assign [l, r) = v.
  /// @return The original segments as vector of (left, right, value).
  std::vector<std::tuple<int, int, T>> assign(int l, int r, T v) {
    if (l == r)
      return {};
    split(l);
    split(r);
    auto it = mp.find(l);
    T t = mp[l];
    std::vector<std::tuple<int, int, T>> seg;
    while (it->first != r) {
      auto nx = next(it);
      seg.push_back({it->first, nx->first, nx->second});
      it = mp.erase(it);
    }
    mp[l] = t;
    mp[r] = v;
    return seg;
  }
};

} // namespace noya