Description

给出数据流$a[1...n]$，要求实现SummaryRanges类以提供三种操作：

• SummaryRanges()：初始化流
• void addNum(int value)：添加value到流中
• int[][] getIntervals()：查询返回若干不相交的区间$[l{o}_i,h{i}_i]$（按照$l{o}_i$排序）

Constraints

• 最多$3\times {10}^4$次addNum(int value)和getIntervals()操作
• 最多${10}^2$次getIntervals()操作

Solution

使用并查集$p$维护区间，使用平衡树$inserted$避免区间端点枚举

Code

class SummaryRanges {
public:

    array<int, 10004> p;
    set<int> inserted;

    SummaryRanges() {
        ranges::fill(p, -1);
    }

    int find(int u) {
        return p[u] == u ? u : find(p[u]);
    }
    
    void addNum(int value) {
        if(~p[value]) return;
        p[value] = value;
        inserted.emplace(value);
        auto l = value - 1;
        auto r = value + 1;

        auto merge = [&](int u, int v) {
            auto pu = find(u), pv = find(v);
            p[pu] = pv;
        };

        if(l >= 0 && p[l] != -1) merge(l, value);
        if(r <= 10000 && p[r] != -1) merge(value, r);
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        auto iter = inserted.begin();
        while(iter != inserted.end()) {
            auto l = *iter;
            auto r = find(l);
            ans.push_back({l, r});
            iter = inserted.lower_bound(r + 1);
        }
        return ans;
    }
};

Link

LeetCode-352 Data Stream as Disjoint Intervals