区间合并

// from leetcode 2276. 统计区间中的整数数目
map<int, int> mp;
int cnt = 0;

void add(int left, int right) {
    for (auto it=mp.lower_bound(left); it!=mp.end() && it->second<=right; mp.erase(it++)) {
        int l = it->second, r = it->first;
        cnt -= r-l+1;
        left = min(left, l);
        right = max(right, r);
    }
    mp[right] = left;
    cnt += right-left+1;
}

int count() {
    return cnt;
}

主要思想是对于新插入的区间，删掉所有它覆盖（含部分覆盖）的区间，然后再插入。

区间的右边界作为键，左边界作为值。 由于map的特性，所有键都是有序的。 第一个大于等于left的键值对就是我们要删除的第一个区间。然后不断删除区间直到区间的左边界大于right为止。

https://codeforces.com/contest/1859/problem/D

珂朵莉树

struct Node_t {
    int l, r;
    mutable int v;

    Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}

    bool operator<(const Node_t &o) const { return l < o.l; }
};

set<Node_t> odt;
// odt.insert(Node_t(0, 1e9+7, 0));

// 二分找到x所在区间[l,r], 分裂为 [l,x-1] [x, r]
auto split(int x) {
    // if (x > n) return odt.end();
    auto it = --odt.upper_bound(Node_t{x, 0, 0});
    if (it->l == x) return it;
    int l = it->l, r = it->r, v = it->v;
    odt.erase(it);
    odt.insert(Node_t(l, x - 1, v));
    return odt.insert(Node_t(x, r, v)).first;
}
// 二分找到l和r所在区间[a,b]与[c,d]并分裂，[a, l-1] [l, b] .... [c, r] [r+1, d]
void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    // odt.erase(itl, itr);
		while (itl != itr) {
        // Perform Operations here
				odt.erase(itl++);
		}
    odt.insert(Node_t(l, r, v));
}

void performance(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; ++itl) {
        // Perform Operations here
    }
}