src/misc/intervalset.hpp

• View this file on GitHub
• Last update: 2026-03-15 19:33:42+09:00
• Include: #include "src/misc/intervalset.hpp"

Depends on

• src/template.hpp

Code

#include "../template.hpp"

struct IntervalSet{
    set<pair<long,long>> st;
    IntervalSet(){
        st.insert(make_pair(-1e18,-1e18));
        st.insert(make_pair(1e18,1e18));
    }
    void add(long l, long r){
        if(l>=r) return ;
        auto it=st.lower_bound(make_pair(l,r));
        it--;
        if(it->fi<=l && l<=it->se){
            chmin(l,it->fi);
            chmax(r,it->se);
        }
        it=st.lower_bound(make_pair(l,r));
        while(1){
            if(l<=it->fi&&it->fi<=r){
                chmax(r,it->se);
                it=st.erase(it);
            }
            else break;
        }
        st.insert(make_pair(l,r));
    }
    void erase(long l, long r){
        if(l>=r) return ;
        long mr=r;
        auto it=st.lower_bound(make_pair(l,-1));
        it--;
        chmax(mr,it->se);
        if(l<it->se){
            long ml=it->fi;
            st.erase(it);
            st.insert(make_pair(ml,l));
        }
        it=st.lower_bound(make_pair(l,-1));
        while(1){
            if(it->fi<=r){
                chmax(mr,it->se);
                it=st.erase(it);
            }
            else break;
        }
        if(r<mr)st.insert(make_pair(r,mr));
    }
    bool in(long x){
        auto it=st.lower_bound(make_pair(x+1,0));
        it--;
        return (x<it->se);
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/misc/intervalset.hpp"

struct IntervalSet{
    set<pair<long,long>> st;
    IntervalSet(){
        st.insert(make_pair(-1e18,-1e18));
        st.insert(make_pair(1e18,1e18));
    }
    void add(long l, long r){
        if(l>=r) return ;
        auto it=st.lower_bound(make_pair(l,r));
        it--;
        if(it->fi<=l && l<=it->se){
            chmin(l,it->fi);
            chmax(r,it->se);
        }
        it=st.lower_bound(make_pair(l,r));
        while(1){
            if(l<=it->fi&&it->fi<=r){
                chmax(r,it->se);
                it=st.erase(it);
            }
            else break;
        }
        st.insert(make_pair(l,r));
    }
    void erase(long l, long r){
        if(l>=r) return ;
        long mr=r;
        auto it=st.lower_bound(make_pair(l,-1));
        it--;
        chmax(mr,it->se);
        if(l<it->se){
            long ml=it->fi;
            st.erase(it);
            st.insert(make_pair(ml,l));
        }
        it=st.lower_bound(make_pair(l,-1));
        while(1){
            if(it->fi<=r){
                chmax(mr,it->se);
                it=st.erase(it);
            }
            else break;
        }
        if(r<mr)st.insert(make_pair(r,mr));
    }
    bool in(long x){
        auto it=st.lower_bound(make_pair(x+1,0));
        it--;
        return (x<it->se);
    }
};

Back to top page