forked from wisdompeak/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path715.Range-Module.cpp
More file actions
64 lines (55 loc) · 1.73 KB
/
Copy path715.Range-Module.cpp
File metadata and controls
64 lines (55 loc) · 1.73 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class RangeModule {
map<int,int>Map;
public:
RangeModule() {
}
void addRange(int left, int right)
{
int leftboundary=left;
int rightboundary = right;
auto iter1 = Map.lower_bound(left);
if (iter1!=Map.begin() && prev(iter1)->second>=left)
{
iter1 = prev(iter1);
leftboundary = iter1->first;
}
auto iter2 = Map.upper_bound(right);
if (iter2!=Map.begin() && prev(iter2)->second >= rightboundary)
rightboundary = prev(iter2)->second;
Map.erase(iter1,iter2);
Map[leftboundary]=rightboundary;
}
bool queryRange(int left, int right)
{
auto iter = Map.upper_bound(left);
return (iter!=Map.begin() && prev(iter)->second>=right);
}
void removeRange(int left, int right)
{
auto iter1 = Map.lower_bound(left);
int start1 = 0, end1 = 0;
if (iter1!=Map.begin() && prev(iter1)->second > left)
{
iter1 = prev(iter1);
start1 = iter1->first;
end1 = left;
}
auto iter2 = Map.upper_bound(right);
int start2 = 0, end2 = 0;
if (iter2!=Map.begin() && prev(iter2)->second > right)
{
start2 = right;
end2 = prev(iter2)->second;
}
Map.erase(iter1, iter2);
if (start1 < end1) Map[start1] = end1;
if (start2 < end2) Map[start2] = end2;
}
};
/**
* 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);
*/