[LeetCode] 715. Range 模块

题目

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。

实现 RangeModule 类:

RangeModule() 初始化数据结构的对象。 void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。 boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。 void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。

代码

typedef pair<int, int> PII;

const int INF = 2e9;

#define x first
#define y second

class RangeModule {
public:
    set<PII> S;
    RangeModule() {
            S.insert({-INF, -INF});
            S.insert({INF, INF});
    }
    
    void addRange(int left, int right) {
        auto i = S.lower_bound({left, -INF});
        i--;
        if(i->y < left) i++;
        if(i->x > right){
            S.insert({left, right});
        }
        else{//有交集
            auto j = i;
            while(j->x <= right) j++;
            j--;
            PII t(min(i->x, left), max(j->y, right));
            while(i!=j){
                auto k=i;
                k++;
                S.erase(i);
                i=k;
            }
            S.erase(i);
            S.insert(t);
        }
    }
    
    bool queryRange(int left, int right) {
        auto i = S.upper_bound({left, INF});
        i--;
        return i->y >= right;
    }

    vector<PII> get(PII a, PII b){
        vector<PII> ans;
        if(a.x < b.x){
            if(a.y > b.y){
                ans.push_back({a.x, b.x});
                ans.push_back({b.y, a.y});
            }else{
                ans.push_back({a.x, b.x});
            }
        }else{
            if(a.y > b.y)   ans.push_back({b.y, a.y});
        }
        return ans;
    }
    
    void removeRange(int left, int right) {
        auto i = S.lower_bound({left, -INF});
        i--;
        if(i->y < left) i++;
        if(i->x <= right)
        {
            auto j = i;
            while(j->x <= right) j++;
            j--;
            auto a = get(*i, {left, right});
            auto b = get(*j, {left, right});
            while(i!=j){
                auto k=i;
                k++;
                S.erase(i);
                i=k;
            }
            S.erase(i);
            for(auto t: a)  S.insert(t);
            for(auto t: b)  S.insert(t);
        }
    }
};

/**
 * 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);
 */