C++ এ রেঞ্জ মডিউল

ধরুন আমরা একটি রেঞ্জ মডিউল চাই। এটি একটি মডিউল যা সংখ্যার রেঞ্জ ট্র্যাক করে। আমাদের কাজ হল নিম্নলিখিত ইন্টারফেসগুলিকে দক্ষভাবে ডিজাইন করা এবং বাস্তবায়ন করা৷

• অ্যাডরেঞ্জ (বাম, ডান)। এটি অর্ধ-খোলা ব্যবধান [বাম, ডানে), সেই ব্যবধানে প্রতিটি বাস্তব সংখ্যা ট্র্যাক করবে। এখন, একটি ব্যবধান যোগ করা যা বর্তমানে ট্র্যাক করা সংখ্যার সাথে আংশিকভাবে ওভারল্যাপ করে সেই ব্যবধানে এমন কোনো সংখ্যা যোগ করা উচিত যা ইতিমধ্যে ট্র্যাক করা হয়নি৷
• কোয়েরি রেঞ্জ (বাম, ডান)। যখন ব্যবধানের প্রতিটি বাস্তব সংখ্যা [বাম, ডানে) বর্তমানে ট্র্যাক করা হচ্ছে তখন এটি সত্য হবে।
• রিমুভ রেঞ্জ(বাম, ডানে), এটি বর্তমানে ব্যবধানে ট্র্যাক করা প্রতিটি বাস্তব সংখ্যাকে ট্র্যাক করা বন্ধ করবে [বাম, ডানে)।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র m সংজ্ঞায়িত করুন
• একটি ফাংশন সংজ্ঞায়িত করুন addRange(), এটি বাম, ডান,
লাগবে
• রিমুভ রেঞ্জ (বাম, ডান)
• m[বাম] :=ডান
• এটি :=অবস্থান যেখানে বামে m এ উপস্থিত রয়েছে
• যদি এটি m-এর প্রথম উপাদানের সমান না হয় এবং এর আগেরটির দ্বিতীয় মানের সমান হয়, তাহলে −
  • (এটি 1 দ্বারা কমিয়ে দিন)
  • এর দ্বিতীয় :=ডান
  • m থেকে বাম মুছে দিন
• যদি এটি m এর শেষ উপাদানের আগের সমান না হয় এবং এর পরের প্রথমটি ডানের সমান হয়, তাহলে −
  • এর সেকেন্ড :=পরের সেকেন্ড(এটি)
  • m থেকে পরবর্তী (এটি) মুছুন
• একটি ফাংশন queryRange() সংজ্ঞায়িত করুন, এটি বাম, ডান,
লাগবে
• এটি :=m এর একটি সাবপার্টের অবস্থান বাম থেকে সব ছোট মান
• যদি m খালি হয় বা এটি m এর প্রথম উপাদানের সমান হয়, তাহলে −
  • মিথ্যে ফেরত দিন
• (এটি 1 দ্বারা কমিয়ে দিন)
• সত্য ফেরত যখন এর সেকেন্ডে>=ডান
• একটি ফাংশন সংজ্ঞায়িত করুন removeRange(), এটি বাম, ডান,
লাগবে
• যদি m খালি হয়, তাহলে −
  • প্রত্যাবর্তন
• এটি :=m এর একটি সাবপার্টের অবস্থান বাম থেকে সমস্ত উপরের মান
• যদি এটি m এর প্রথম উপাদানের সমান না হয়, তাহলে −
  • (এটি 1 দ্বারা কমিয়ে দিন)
• একটি অ্যারে v
সংজ্ঞায়িত করুন
• যখন (এটি m এর শেষ উপাদানের সমান নয় এবং এর প্রথম
• যদি এর প্রথম <বাম এবং দ্বিতীয়টির> বাম হয়, তাহলে −
  • temp :=এর সেকেন্ড
  • এর দ্বিতীয় :=বাকি
  • যদি temp> right, তারপর: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