Untitled

 avatar
unknown
c_cpp
a year ago
3.2 kB
11
Indexable
#include<set>
#include <iostream>
#include <utility>
using namespace std;
class RangeModule {
private:
public:
    set<pair<int, int>> ranges;
    RangeModule() {
    }

    void addRange(int left, int right) {
        if (right < left)
            return;
        // since it's already balanced, all ranges in set are non intersecting, so the point 'left' will intersects at most 1 step left needed
        int new_left = left, new_right = right;
        auto left_remove = ranges.end();
        auto it = ranges.upper_bound({left, 1e9});
        if (it != ranges.begin()) {
            --it;
            if (it->second >= left) { // it->first guaranteed to be less than or equal left anyways, so check on it->second only
                // prev range does intersect
                new_left = it->first;
                left_remove = it;
            }
        }
        auto right_remove = ranges.end();
        it = ranges.upper_bound({right, 1e9});
        if (it != ranges.begin()) {
            --it;
            if (it->second >= right) { // it->first guaranteed to be less than or equal right anyways, so check on it->second only
                // prev range does intersect
                new_right = it->second;
                ++it;
                right_remove = it;
            }
        }
        if (left_remove != ranges.end())
            ranges.erase(left_remove, right_remove);
        ranges.insert({new_left, new_right});
    }

    bool queryRange(int left, int right) {
        auto it = ranges.upper_bound({left, 1e9});
        if (it != ranges.begin()) {
            --it;
            return it->first <= left && right <= it->second;
        }
        return false;
    }

    void removeRange(int left, int right) {
        if (ranges.empty())
            return;
        int prevLeft = left;
        while (true) {
            auto it = ranges.upper_bound({prevLeft, -1});
            if (it != ranges.begin())
                --it;
            auto cur = *it;
            if (cur.second <= prevLeft) // prevLeft is already greater than or equal cur.first
                break;
            ranges.erase(it);
            addRange(cur.first, left);
            addRange(right, cur.second);
            prevLeft = cur.second + 1;
        }
    }
};

void print(RangeModule *x) {
    for (auto p: x->ranges){
        cout << p.first << " " << p.second << endl;
    }
    cout << endl;
}


int main() {
//    ["RangeModule","addRange","addRange","addRange","queryRange","queryRange","queryRange","removeRange","queryRange"]
//    [[],[10,180],[150,200],[250,500],[50,100],[180,300],[600,1000],[50,150],[50,100]]
    RangeModule *x = new RangeModule();
//    x->addRange(10, 20);
//    print(x);
//    x->removeRange(14, 16);
//    print(x);
//    cout << x->queryRange(10, 14) << endl;
//    cout << x->queryRange(13, 15) << endl;
//    cout << x->queryRange(16, 17) << endl;
//    return 0;
//
    x->addRange(10, 180);
    x->addRange(150, 200);
    x->addRange(250, 500);
    print(x);
    x->removeRange(50, 150);
    print(x);
    cout << x->queryRange(50, 100) << endl;
    return 0;
}

//10  - 180
//250 -  500
Editor is loading...
Leave a Comment