在线区间问题

单点修改，查询合并地区间

每次只添加一个点，随时查询当前的合并后的所有区间。

离线区间合并只需要对所有区间按照起点排序，之后遍历一遍即可，但是在线区间合并则无法进行离线的排序！因此需要用有序的数据结构存储现有的区间。需要分五类讨论：

class SummaryRanges {
private:
    map<int, int> intervals;

public:
    SummaryRanges() {}

    void addNum(int val) {
        // 找到 l1 最小的且满足 l1 > val 的区间 interval1 = [l1, r1]
        // 如果不存在这样的区间，interval1 为尾迭代器
        auto interval1 = intervals.upper_bound(val);
        // 找到 l0 最大的且满足 l0 <= val 的区间 interval0 = [l0, r0]
        // 在有序集合中，interval0 就是 interval1 的前一个区间
        // 如果不存在这样的区间，interval0 为尾迭代器
        auto interval0 = (interval1 == intervals.begin() ? intervals.end() : prev(interval1));

        if (interval0 != intervals.end() && interval0->first <= val && val <= interval0->second) {
            // 情况一
            return;
        }
        else {
            bool left_aside = (interval0 != intervals.end() && interval0->second + 1 == val);
            bool right_aside = (interval1 != intervals.end() && interval1->first - 1 == val);
            if (left_aside && right_aside) {
                // 情况四
                int left = interval0->first, right = interval1->second;
                intervals.erase(interval0);
                intervals.erase(interval1);
                intervals.emplace(left, right);
            }
            else if (left_aside) {
                // 情况二
                ++interval0->second;
            }
            else if (right_aside) {
                // 情况三
                int right = interval1->second;
                intervals.erase(interval1);
                intervals.emplace(val, right);
            }
            else {
                // 情况五
                intervals.emplace(val, val);
            }
        }
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for (const auto& [left, right]: intervals) {
            ans.push_back({left, right});
        }
        return ans;
    }
};

Range模块

每次修改一个区间（添加或删除），随时查询某个区间是否被完全填充。

线段树的经典应用，由于数据范围1e9，需要动态分配线段树。

class RangeModule {
public:
    // dynamically allocated segment tree
    struct node {
        int l, r, v, z;
        node *ll, *rr;
        node(int _l, int _r, int _v = 0): l(_l), r(_r), v(_v), z(0), ll(nullptr), rr(nullptr) {}
        int m() { return (l+r)/2; }
    };

    void pushdown(node* n) {
        if (n->z) {
            n->ll->v = n->v;
            n->ll->z = 1;
            n->rr->v = n->v;
            n->rr->z = 1;
            n->z = 0;
        }
    }

    void pushup(node* n) {
        n->v = n->ll->v && n->rr->v;
    }

    void modify(node* n, int l, int r, int v) {
        //cout << "mod " << v << " | [" << n->l << ", " << n->r << "], [" << l << ", " <<r << "]" << endl;
        if (n->l == l && n->r == r) {
            n->v = v;
            n->z = 1;
            return;
        }
        int nm = n->m();
        if (n->ll == nullptr) n->ll = new node(n->l, nm, n->v);
        if (n->rr == nullptr) n->rr = new node(nm + 1, n->r, n->v);
        pushdown(n);
        if (r <= nm) modify(n->ll, l, r, v);
        else if (l > nm) modify(n->rr, l, r, v);
        else {
            modify(n->ll, l, nm, v);
            modify(n->rr, nm + 1, r, v);
        }
        pushup(n);
    }

    bool query(node* n, int l, int r) {
        //cout << "query " << "[" << n->l << ", " << n->r << "], [" << l << ", " <<r << "] " << n->v << endl;
        if (n->l == l && n->r == r) {
            return n->v;
        }
        int nm = n->m();
        if (n->ll == nullptr) n->ll = new node(n->l, nm, n->v);
        if (n->rr == nullptr) n->rr = new node(nm + 1, n->r, n->v);
        pushdown(n);
        if (r <= nm) return query(n->ll, l, r);
        else if (l > nm) return query(n->rr, l, r);
        else return query(n->ll, l, nm) && query(n->rr, nm + 1, r);
    }

    node* root = new node(0, 1e9, 0);

    //////////////////////////////////////

    RangeModule() {}

    void addRange(int left, int right) {
        modify(root, left, right- 1, 1);
    }

    bool queryRange(int left, int right) {
        return query(root, left, right - 1);
    }

    void removeRange(int left, int right) {
        modify(root, left, right - 1, 0);
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */

也可以用set维护有序的数据结构：

class RangeModule {
    set<pair<int,int>> s;
public:
    RangeModule() {}

    void addRange(int left, int right) {
        auto it = s.lower_bound({left, left});
        if (it != s.begin()) it--;
        while (it != s.end() && it->first <= right){
            if (it->second < left) {
                it++;
                continue;
            }
            left = min(it->first, left);
            right = max(it->second, right);
            s.erase(it++);
        }
        s.insert(make_pair(left, right));
    }

    bool queryRange(int left, int right) {
        auto it = s.lower_bound({left, left});
        if (it->first <= left && it->second >= right) return true;
        if (it != s.begin()) {
            --it;  
            if (it->first <= left && it->second >= right) return true;
        }
        return false;
    }

    void removeRange(int left, int right) {
        if (s.empty()) return;
        auto it = s.lower_bound({left, left});
        if (it != s.begin()) it--;
        while (it != s.end() && it->first < right){
            if (it->second <= left){
                it++;
                continue;
            }
            if (it->first < left) s.insert({it->first, left});
            if (it->second > right) s.insert({right, it->second});
            s.erase(it++);
        }
    }
};