library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Range Union Set
(DataStructure/rangeunionset.hpp)

• View this file on GitHub
• Last update: 2025-06-08 13:20:31+09:00
• Include: #include "DataStructure/rangeunionset.hpp"

使い方

RangeUnionSet(): 空のデータ構造を作成。テンプレートに型と最大値を指定。
void insert(T L,T R): 半開区間 $[L,R)$ を整数集合に追加。
void erase(T L,T R): 半開区間 $[L,R)$ を整数集合から削除。
T mex(T x): 整数集合の mex を求める。

Code

#pragma once

template <typename T, T mx> struct RangeUnionSet {
    map<T, T> data;
    RangeUnionSet() {}
    void insert(T lb, T rb) {
        auto L = data.upper_bound(lb), R = data.upper_bound(rb);
        if (L != data.begin() and lb <= prev(L)->second)
            L--;
        if (L != R) {
            chmin(lb, L->first);
            chmax(rb, prev(R)->second);
            data.erase(L, R);
        }
        data[lb] = rb;
    }
    void erase(T lb, T rb) {
        auto L = data.upper_bound(lb), R = data.upper_bound(rb);
        if (L != data.begin() and lb <= prev(L)->second)
            L--;
        if (L == R)
            return;
        T nl = min(lb, L->first), nr = max(rb, prev(R)->second);
        data.erase(L, R);
        if (nl < lb)
            data[nl] = lb;
        if (rb < nr)
            data[rb] = nr;
    }
    T mex(T x) const {
        auto it = data.lower_bound(x);
        if (it != data.begin() and prev(it)->second > x)
            it--;
        if (it == data.end())
            return mx;
        return max(x, it->first);
    }
    vector<pair<T, T>> get() {
        vector<pair<T, T>> ret;
        for (auto &[L, R] : data)
            ret.push_back({L, R});
        return ret;
    }
};

/**
 * @brief Range Union Set
 * @docs docs/rangeunionset.md
 */

#line 2 "DataStructure/rangeunionset.hpp"

template <typename T, T mx> struct RangeUnionSet {
    map<T, T> data;
    RangeUnionSet() {}
    void insert(T lb, T rb) {
        auto L = data.upper_bound(lb), R = data.upper_bound(rb);
        if (L != data.begin() and lb <= prev(L)->second)
            L--;
        if (L != R) {
            chmin(lb, L->first);
            chmax(rb, prev(R)->second);
            data.erase(L, R);
        }
        data[lb] = rb;
    }
    void erase(T lb, T rb) {
        auto L = data.upper_bound(lb), R = data.upper_bound(rb);
        if (L != data.begin() and lb <= prev(L)->second)
            L--;
        if (L == R)
            return;
        T nl = min(lb, L->first), nr = max(rb, prev(R)->second);
        data.erase(L, R);
        if (nl < lb)
            data[nl] = lb;
        if (rb < nr)
            data[rb] = nr;
    }
    T mex(T x) const {
        auto it = data.lower_bound(x);
        if (it != data.begin() and prev(it)->second > x)
            it--;
        if (it == data.end())
            return mx;
        return max(x, it->first);
    }
    vector<pair<T, T>> get() {
        vector<pair<T, T>> ret;
        for (auto &[L, R] : data)
            ret.push_back({L, R});
        return ret;
    }
};

/**
 * @brief Range Union Set
 * @docs docs/rangeunionset.md
 */

Back to top page