범위 모듈이 필요하다고 가정합니다. 이것은 숫자의 범위를 추적하는 모듈입니다. 우리의 임무는 다음 인터페이스를 효율적인 방식으로 설계하고 구현하는 것입니다.
- addRange(왼쪽, 오른쪽). 이것은 반개방 간격[왼쪽, 오른쪽)이 되어 해당 간격의 모든 실수를 추적합니다. 이제 현재 추적되는 숫자와 부분적으로 겹치는 간격을 추가하면 간격에 아직 추적되지 않은 숫자가 추가되어야 합니다.
- queryRange(왼쪽, 오른쪽) . 간격 [왼쪽, 오른쪽)의 모든 실수가 현재 추적 중이면 true를 반환합니다.
- removeRange(left, right), [left, right) 구간에서 현재 추적 중인 모든 실수 추적을 중지합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 하나의 지도 정의
- addRange() 함수를 정의하면 왼쪽, 오른쪽,
- removeRange(왼쪽, 오른쪽)
- m[왼쪽] :=오른쪽
- it :=왼쪽이 m 단위로 존재하는 위치
- m의 첫 번째 요소와 같지 않고 이전의 두 번째 값이 왼쪽과 같으면 -
- (1씩 감소)
- 두 번째 :=맞아
- m에서 왼쪽 삭제
- m의 마지막 요소의 이전 요소와 같지 않고 다음 요소의 첫 번째 요소가 오른쪽 요소와 같으면 -
- 두 번째:=next(it)의 두 번째
- m에서 다음(it) 삭제
- queryRange() 함수를 정의하면 왼쪽, 오른쪽,
- it :=m의 하위 부분의 위치는 모두 왼쪽보다 작은 값입니다.
- m이 비어 있거나 m의 첫 번째 요소와 같으면 -
- 거짓 반환
- (1씩 감소)
- 두 번째 경우 true를 반환>=오른쪽
- removeRange() 함수를 정의하면 왼쪽, 오른쪽,
- m이 비어 있으면 -
- 반환
- it :=m의 하위 부분의 위치는 모두 왼쪽보다 높은 값입니다.
- m의 첫 번째 요소와 같지 않으면 -
- (1씩 감소)
- 배열 정의 v
- 동안(m의 마지막 요소와 같지 않고 첫 번째 요소가
- 첫 번째 <왼쪽 및 두 번째> 왼쪽이면 -
- temp :=두 번째
- 두 번째 :=왼쪽
- temp> 맞으면 m[right] :=temp
- 그렇지 않으면 처음에>=왼쪽일 때, 그 다음 −
- v 끝에 첫 번째 삽입
- 두 번째 경우> 맞으면 -
- m[right] :=두 번째
- (1씩 증가)
- 첫 번째 <왼쪽 및 두 번째> 왼쪽이면 -
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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