\(map\) 可用于维护所有标记的数，但只支持单点修改和单点查询，而 \(RangeManager\) 则能在 \(map\) 的基础上通过将连续值的标记转换为区间的标记，从而额外支持区间修改和区间查询。
\(add\_range(\{l,r\})\) ：区间修改，标记闭区间 \([l, r]\) 的每个数，时间复杂度：\(O(logn)\) 。
\(remove\_range(\{l,r\})\) ：区间修改，去除闭区间 \([l, r]\) 每个数的标记，时间复杂度：\(O(logn)\) 。
\(any\_of(\{l, r\})\)：区间查询，查询区间 \([l, r]\) 内是否存在某个数被标记，若存在则返回与 \([l, r]\) 相交且左端点最小的区间的迭代器，否则返回 \(end()\) ，时间复杂度：\(O(logn)\) 。
\(all\_of(\{l, r\})\)：区间查询，查询区间 \([l, r]\) 内是否每个数都被标记，若是则返回包含 \([l, r]\) 的区间的迭代器，否则返回 \(end\) ，时间复杂度：\(O(logn)\) 。
\(length()\)：返回被标记的数的总数，时间复杂度：\(O(1)\) 。
\(size()\)：返回被标记的区间的总数，时间复杂度：\(O(1)\) 。
\(clear()\)：清空 \(RangeManager\) ，时间复杂度：\(O(n)\) 。
\(lower\_bound(l)\)：若存在，则返回第一个左端点大于等于 \(l\) 的区间的迭代器，否则返回 \(end()\) ，时间复杂度：\(O(logn)\) 。
\(upper\_bound(l)\)：若存在，则返回第一个左端点大于 \(l\) 的区间的迭代器，否则返回 \(end()\) ，时间复杂度：\(O(logn)\) 。
namespace OY {
template <typename Tp>
struct RangeManager {
using iterator = typename std::map<Tp, Tp>::iterator;
using const_iterator = typename std::map<Tp, Tp>::const_iterator;
Tp m_length = 0;
std::map<Tp, Tp> m_segs;
static Tp length_of(const std::pair<Tp, Tp> &range) { return range.second - range.first + 1; }
void add_range(std::pair<Tp, Tp> range) {
auto it = upper_bound(range.first);
if (it != begin()) {
if ((--it)->second + 1 >= range.first) {
if (it->second >= range.second) return;
range.first = it->first;
m_length -= length_of(*it);
it = m_segs.erase(it);
} else ++it;
}
while (it != end() && it->first <= range.second + 1) {
if (it->second > range.second) range.second = it->second;
m_length -= length_of(*it);
it = m_segs.erase(it);
}
m_length += length_of(*m_segs.emplace(range.first, range.second).first);
}
void remove_range(std::pair<Tp, Tp> range) {
std::vector<std::pair<Tp, Tp>> deleted, inserted;
iterator it = m_segs.upper_bound(range.first);
if (it != begin()) {
if ((--it)->second >= range.first) {
m_length -= it->second - it->first + 1;
if (it->second >= range.second && it->second > range.second) {
m_length += it->second - range.second;
m_segs.emplace(range.second + 1, it->second);
if (it->first < range.first) {
it->second = range.first - 1;
m_length += it->second - it->first + 1;
++it;
} else m_segs.erase(it);
return;
}
if (it->first < range.first) {
it->second = range.first - 1;
m_length += it->second - it->first + 1;
it++;
} else it = m_segs.erase(it);
} else it++;
}
while (it != end() && it->first <= range.second) {
m_length -= it->second - it->first + 1;
if (it->second > range.second) {
m_segs.emplace(range.second + 1, it->second);
m_length += it->second - range.second;
}
it = m_segs.erase(it);
}
}
const_iterator any_of(const std::pair<Tp, Tp> &range) const {
const_iterator it = upper_bound(range.second);
if (it == begin()) return end();
if ((--it)->second < range.first) return end();
return it;
}
const_iterator all_of(const std::pair<Tp, Tp> &range) const {
const_iterator it = upper_bound(range.second);
if (it == begin()) return end();
if ((--it)->first > range.first || it->second < range.second) return end();
return it;
}
Tp length() const { return m_length; }
void clear() { m_segs.clear(); }
auto size() const -> decltype(m_segs.size()) { return m_segs.size(); }
auto begin() const -> decltype(m_segs.begin()) { return m_segs.begin(); }
auto end() const -> decltype(m_segs.end()) { return m_segs.end(); }
auto lower_bound(const Tp &key) const -> decltype(m_segs.lower_bound(key)) { return m_segs.lower_bound(key); }
auto upper_bound(const Tp &key) const -> decltype(m_segs.upper_bound(key)) { return m_segs.upper_bound(key); }
};
template <typename Ostream, typename Tp>
Ostream &operator<<(Ostream &out, const RangeManager<Tp> &x) {
out << '[';
for (auto it = x.begin(); it != x.end(); ++it) {
if (it != x.begin()) out << ", ";
out << "[" << it->first << ", " << it->second << "]";
}
return out << ']';
}
}