2276.统计区间中的整数数目

链接：2276.统计区间中的整数数目
难度：Hard
标签：设计、线段树、有序集合
简介：给你区间的 空 集，请你设计并实现满足要求的数据结构：新增：添加一个区间到这个区间集合中。统计：计算出现在 至少一个 区间中的整数个数。

题解 1 - cpp

• 编辑时间：2023-12-16
• 执行用时：432ms
• 内存消耗：181.94MB
• 编程语言：cpp
• 解法介绍：平衡二叉树。

class CountIntervals {
public:
    map<int, int> tree;
    int sum;
    CountIntervals(): sum(0) {
        tree[0] = 0;
        tree[INT_MAX] = INT_MAX;
    }
    int count() {
        return sum;
    }
    void add(int left, int right) {
        auto it = tree.lower_bound(left);
        auto prev = it;
        prev--;
        if (prev->second >= left) {
            left = min(left, prev->first);
            right = max(right, prev->second);
            sum -= prev->second - prev->first + 1;
            it = tree.erase(prev);
        }
        while (right >= it->first) {
            right = max(right, it->second);
            sum -= it->second - it->first + 1;
            it = tree.erase(it);
        }
        tree[left] = right;
        sum += right - left + 1;
    }
};