Range Union Set
(DataStructure/rangeunionset.hpp)

• View this file on GitHub
• Last update: 2022-02-05 01:38:09+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);
    }
};

/**
 * @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);
    }
};

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

Back to top page