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