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)\).
Implementation¶
当前头文件，省略 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 <utility>
#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) { split_at(x); }
/// @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 {};
auto left = split_at(l);
auto right = split_at(r);
std::vector<std::tuple<int, int, T>> seg;
for (auto it = left; it != right;) {
auto nx = std::next(it);
seg.push_back({it->first, nx->first, nx->second});
it = nx;
}
mp.erase(std::next(left), right);
right->second = std::move(v);
return seg;
}
private:
typename std::map<int, T>::iterator split_at(int x) {
auto it = mp.lower_bound(x);
if (it->first == x)
return it;
return mp.emplace_hint(it, x, it->second);
}
};
} // namespace noya
// NOYA_CONSECUTIVE_SEGMENT_HPP
#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 <utility>
#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) { split_at(x); }
/// @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 {};
auto left = split_at(l);
auto right = split_at(r);
std::vector<std::tuple<int, int, T>> seg;
for (auto it = left; it != right;) {
auto nx = std::next(it);
seg.push_back({it->first, nx->first, nx->second});
it = nx;
}
mp.erase(std::next(left), right);
right->second = std::move(v);
return seg;
}
private:
typename std::map<int, T>::iterator split_at(int x) {
auto it = mp.lower_bound(x);
if (it->first == x)
return it;
return mp.emplace_hint(it, x, it->second);
}
};
} // namespace noya
#endif // NOYA_CONSECUTIVE_SEGMENT_HPP
/// @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 <utility>
#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) { split_at(x); }
/// @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 {};
auto left = split_at(l);
auto right = split_at(r);
std::vector<std::tuple<int, int, T>> seg;
for (auto it = left; it != right;) {
auto nx = std::next(it);
seg.push_back({it->first, nx->first, nx->second});
it = nx;
}
mp.erase(std::next(left), right);
right->second = std::move(v);
return seg;
}
private:
typename std::map<int, T>::iterator split_at(int x) {
auto it = mp.lower_bound(x);
if (it->first == x)
return it;
return mp.emplace_hint(it, x, it->second);
}
};
} // namespace noya
// NOYA_CONSECUTIVE_SEGMENT_HPP