Untitled
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