区間をmapで管理するやつ
(datastructure/segmentmap.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "datastructure/segmentmap.hpp"
• Link: https://satanic0258.github.io/snippets/data-structure/SegmentMap.html

概要

閉区間をmapで管理するやつ.

計算量

• 各クエリ : $O(\log n)$

使用例

• SegmentMap mp(flg = true) : 「区間をmapで管理するやつ」を準備.
  • flg : $[l, c]$と$[c + 1, r]$をマージするかどうか.
• mp.get(p) : $p$を含む区間を返す. (存在しないならmp.end())
• mp.insert(l, r) : 閉区間$[l, r]$を追加する.
• mp.remove(l, r) : 閉区間$[l, r]$を取り除く.
• mp.same(p, q) : $2$点$p$, $q$が同じ区間にあればtrue.

Code

/**
* @brief 区間をmapで管理するやつ
* @note 閉区間であることに注意
* @docs docs/datastructure/segmentmap.md
* @see https://satanic0258.github.io/snippets/data-structure/SegmentMap.html
*/

struct SegmentMap : public map<long long, long long> {
    bool flg_merge;
    SegmentMap(bool flg_merge = true)
        : flg_merge(flg_merge) {}
    auto get(long long p) const {
        auto itr = upper_bound(p);
        if (itr == begin() or (--itr)->second < p) return end();
        return itr;
    }
    void insert(long long l, long long r) {
        auto itr_l = upper_bound(l), itr_r = upper_bound(r + flg_merge);
        if (itr_l != begin()) {
            if ((--itr_l)->second < l - flg_merge) ++itr_l;
        }
        if (itr_l != itr_r) {
            l = min(l, itr_l->first);
            r = max(r, prev(itr_r)->second);
            erase(itr_l, itr_r);
        }
        (*this)[l] = r;
    }
    void remove(long long l, long long r) {
        auto itr_l = upper_bound(l), itr_r = upper_bound(r);
        if (itr_l != begin()) {
            if ((--itr_l)->second < l) ++itr_l;
        }
        if (itr_l == itr_r) return;
        int tl = min(l, itr_l->first), tr = max(r, prev(itr_r)->second);
        erase(itr_l, itr_r);
        if (tl < l) (*this)[tl] = l - 1;
        if (r < tr) (*this)[r + 1] = tr;
    }
    bool same(long long p, long long q) const {
        const auto&& itr = get(p);
        return itr != end() and itr->first <= q and q <= itr->second;
    }
};

#line 1 "datastructure/segmentmap.hpp"
/**
* @brief 区間をmapで管理するやつ
* @note 閉区間であることに注意
* @docs docs/datastructure/segmentmap.md
* @see https://satanic0258.github.io/snippets/data-structure/SegmentMap.html
*/

struct SegmentMap : public map<long long, long long> {
    bool flg_merge;
    SegmentMap(bool flg_merge = true)
        : flg_merge(flg_merge) {}
    auto get(long long p) const {
        auto itr = upper_bound(p);
        if (itr == begin() or (--itr)->second < p) return end();
        return itr;
    }
    void insert(long long l, long long r) {
        auto itr_l = upper_bound(l), itr_r = upper_bound(r + flg_merge);
        if (itr_l != begin()) {
            if ((--itr_l)->second < l - flg_merge) ++itr_l;
        }
        if (itr_l != itr_r) {
            l = min(l, itr_l->first);
            r = max(r, prev(itr_r)->second);
            erase(itr_l, itr_r);
        }
        (*this)[l] = r;
    }
    void remove(long long l, long long r) {
        auto itr_l = upper_bound(l), itr_r = upper_bound(r);
        if (itr_l != begin()) {
            if ((--itr_l)->second < l) ++itr_l;
        }
        if (itr_l == itr_r) return;
        int tl = min(l, itr_l->first), tr = max(r, prev(itr_r)->second);
        erase(itr_l, itr_r);
        if (tl < l) (*this)[tl] = l - 1;
        if (r < tr) (*this)[r + 1] = tr;
    }
    bool same(long long p, long long q) const {
        const auto&& itr = get(p);
        return itr != end() and itr->first <= q and q <= itr->second;
    }
};

Back to top page