C ++中的范围模块
假设我们要一个范围模块。这是一个跟踪数字范围的模块。我们的任务是以有效的方式设计和实现以下接口。
addRange(left,right)。这将是半开间隔（左，右），跟踪该间隔中的每个实数。现在，添加一个与当前跟踪的数字部分重叠的间隔，应该在间隔中添加尚未跟踪的任何数字。
queryRange(left,right)。当前正在跟踪间隔[left，right）中的每个实数时，它将返回true。
removeRange(left,right)，这将停止跟踪间隔[left，right）中当前正在跟踪的每个实数。
为了解决这个问题，我们将遵循以下步骤-
定义一张映射
定义一个函数addRange()，它将取左，右，
removeRange（左，右）
m[左]：=右
它：=m处左边的位置
如果它不等于m的第一个元素，并且它的前一个的第二个值与left相同，则-
（减少1）
第二个：=对
从m删除左
如果它不等于m的最后一个元素的前一个且它的下一个的第一个与右相同，则-
秒：=下一个秒
从m删除next(it)
定义一个函数queryRange()，它将取左，右，
它：=m的子部分的位置的所有值均小于左值
如果m为空或与m的第一个元素相同，则-
返回假
（减少1）
当第二个>=right时返回true
定义一个函数removeRange()，它将取左，右，
如果m为空，则-
返回
它：=m的子部分的位置都比左边高
如果它不等于m的第一个元素，则-
（减少1）
定义数组v
while（它不等于m的最后一个元素，并且它的第一个<右），执行-
在v的末尾插入第一行
如果第二个>对，则-
m[right]：=第二秒
temp：=秒
第二个：=左
如果temp>right，则：m[right]：=temp
如果第一个<左边，第二个>左边，则-
否则，当它首先>=左时，然后-
（增加1）
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
从m删除v[i]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class RangeModule {
public:
map <int, int> m;
RangeModule() {
}
void addRange(int left, int right) {
removeRange(left, right);
m[left] = right;
map <int, int> :: iterator it = m.find(left);
if(it != m.begin() && prev(it)->second == left){
it--;
it->second = right;
m.erase(left);
}
if(it != prev(m.end()) && next(it)->first == right){
it->second = next(it)->second;
m.erase(next(it));
}
}
bool queryRange(int left, int right) {
map <int, int> :: iterator it = m.upper_bound(left);
if(m.empty() || it == m.begin())return false;
it--;
return it->second >= right;
}
void removeRange(int left, int right) {
if(m.empty())return;
map <int, int> :: iterator it = m.lower_bound(left);
if(it != m.begin())it--;
vector <int> v;
while(it != m.end() && it->first < right){
if(it->first < left && it->second > left){
int temp = it->second;
it->second = left;
if(temp > right){
m[right] = temp;
}
}else if(it->first >= left){
v.push_back(it->first);
if(it->second > right){
m[right] = it->second;
}
}
it++;
}
for(int i = 0; i < v.size(); i++){
m.erase(v[i]);
}
}
};
main(){
RangeModule ob;
ob.addRange(10,20);
ob.removeRange(14,16);
cout << (ob.queryRange(10,14)) << endl;
cout << (ob.queryRange(13,15)) << endl;
cout << (ob.queryRange(16,17));
}输入项
Add range (10,20) Remove Range (14,16) Check ranges (10,14), (13,15), (16,17)
输出结果
1 0 1