Giả sử chúng ta muốn có một Mô-đun Phạm vi. Đây là một mô-đun theo dõi các dải số. Nhiệm vụ của chúng tôi là thiết kế và triển khai các giao diện sau một cách hiệu quả.
- addRange (trái, phải). Đây sẽ là khoảng thời gian nửa mở [trái, phải), theo dõi mọi số thực trong khoảng đó. Bây giờ, việc thêm một khoảng trùng lặp một phần với các số hiện đang được theo dõi sẽ thêm bất kỳ số nào trong khoảng chưa được theo dõi.
- queryRange (trái, phải). Điều này sẽ trả về true khi mọi số thực trong khoảng [trái, phải) hiện đang được theo dõi.
- removeRange (trái, phải), điều này sẽ ngừng theo dõi mọi số thực hiện đang được theo dõi trong khoảng thời gian [trái, phải).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một bản đồ m
- Xác định một hàm addRange (), hàm này sẽ chuyển sang trái, phải,
- removeRange (trái, phải)
- m [left]:=right
- it:=vị trí mà bên trái hiện diện trong m
- nếu nó không bằng phần tử đầu tiên của m và giá trị thứ hai của phần trước đó bằng bên trái, thì -
- (giảm nó đi 1)
- thứ hai của nó:=right
- xóa bên trái khỏi m
- nếu nó không bằng phần tử trước của phần tử cuối cùng của m và phần tử đầu tiên của phần tử tiếp theo bằng bên phải, thì -
- giây của nó:=giây của tiếp theo (nó)
- xóa tiếp theo (nó) khỏi m
- Xác định một hàm queryRange (), hàm này sẽ chuyển sang trái, phải,
- it:=vị trí của một phần con của m tất cả đều có giá trị nhỏ hơn bên trái
- nếu m trống hoặc nó giống với phần tử đầu tiên của m, thì -
- trả về false
- (giảm nó đi 1)
- trả về true khi đến giây thứ hai> =right
- Xác định một hàm removeRange (), hàm này sẽ chuyển sang trái, phải,
- nếu m trống, thì -
- trở lại
- it:=vị trí của một phần con của m có tất cả giá trị phía trên bên trái
- nếu nó không bằng phần tử đầu tiên của m, thì -
- (giảm nó đi 1)
- Xác định một mảng v
- while (nó không bằng phần tử cuối cùng của m và phần tử đầu tiên của nó
- nếu đầu tiên của nó
left, thì - - temp:=giây của nó
- thứ hai của nó:=left
- if temp> right, then:m [right]:=temp
- ngược lại khi đầu tiên của nó> =left, sau đó -
- Chèn đầu tiên của nó vào cuối v
- nếu thứ hai của nó> đúng, thì -
- m [right]:=giây của nó
- (tăng nó lên 1)
- nếu đầu tiên của nó
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
Add range (10,20) Remove Range (14,16) Check ranges (10,14), (13,15), (16,17)
Đầu ra
1 0 1