मान लीजिए हम एक रेंज मॉड्यूल चाहते हैं। यह एक मॉड्यूल है जो संख्याओं की श्रेणियों को ट्रैक करता है। हमारा काम निम्नलिखित इंटरफेस को कुशल तरीके से डिजाइन और कार्यान्वित करना है।
- एडरेंज (बाएं, दाएं)। यह आधा खुला अंतराल [बाएं, दाएं] होगा, जो उस अंतराल में प्रत्येक वास्तविक संख्या को ट्रैक करेगा। अब, वर्तमान में ट्रैक की गई संख्याओं के साथ आंशिक रूप से ओवरलैप होने वाले अंतराल को जोड़ने से उस अंतराल में कोई भी संख्या जोड़नी चाहिए जो पहले से ट्रैक नहीं की गई है।
- queryRange(बाएं, दाएं)। यह तब सही होगा जब अंतराल में प्रत्येक वास्तविक संख्या [बाएं, दाएं) को वर्तमान में ट्रैक किया जा रहा है।
- removeRange(बाएं, दाएं), यह अंतराल [बाएं, दाएं) में वर्तमान में ट्रैक किए जा रहे प्रत्येक वास्तविक नंबर को ट्रैक करना बंद कर देगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक मानचित्र को परिभाषित करें मी
- एक फ़ंक्शन को परिभाषित करें addRange(), यह बाएँ, दाएँ ले जाएगा,
- रिमूव रेंज (बाएं, दाएं)
- मी[बाएं] :=दाएं
- यह :=वह स्थान जहां बाईं ओर मी में मौजूद है
- यदि यह m के पहले तत्व के बराबर नहीं है और इसके पिछले के दूसरे मान के बराबर है, तो −
- (इसे 1 से घटाएं)
- इसका दूसरा:=दाएं
- m से बाईं ओर हटाएं
- यदि यह m के अंतिम तत्व के पिछले तत्व के बराबर नहीं है और इसके अगले तत्व का पहला दायें के समान है, तो −
- इसका दूसरा :=अगले का दूसरा (यह)
- m से अगला (इसे) हटाएं
- फ़ंक्शन को परिभाषित करें queryRange(), यह बाएँ, दाएँ ले जाएगा,
- it :=m के उप-भाग का स्थान बाएँ से सभी छोटे मान
- यदि m खाली है या यह m के पहले तत्व के समान है, तो −
- झूठी वापसी
- (इसे 1 से घटाएं)
- सही लौटें जब इसका दूसरा भाग>=दाएं
- एक फ़ंक्शन को परिभाषित करें removeRange(), यह बाएँ, दाएँ ले जाएगा,
- यदि मी खाली है, तो −
- वापसी
- यह :=बाएं से सभी ऊपरी मान m के उप-भाग का स्थान
- यदि यह m के पहले तत्व के बराबर नहीं है, तो −
- (इसे 1 से घटाएं)
- एक सरणी v परिभाषित करें
- जबकि (यह एम के अंतिम तत्व के बराबर नहीं है और इसके पहले <दाएं), करते हैं −
- यदि इसमें से पहला <बाएँ और दूसरा> बाएँ, तो −
- अस्थायी:=इसका दूसरा
- इसका दूसरा :=बायां
- यदि अस्थायी> दाएँ, तो:m[दाएँ] :=अस्थायी
- अन्यथा जब इसमें से पहला>=छोड़ दिया, फिर −
- v के अंत में इसे पहले डालें
- यदि इसका दूसरा> सही है, तो −
- m[दाएं] :=दूसरा
- (इसे 1 से बढ़ाएं)
- यदि इसमें से पहला <बाएँ और दूसरा> बाएँ, तो −
- इनिशियलाइज़ i :=0 के लिए, जब i
करें - 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