C++の範囲モジュール

範囲モジュールが必要だとします。これは、数値の範囲を追跡するモジュールです。私たちの仕事は、次のインターフェースを効率的に設計および実装することです。

• addRange（左、右）。これにより、ハーフオープン間隔[左、右）が作成され、その間隔内のすべての実数が追跡されます。現在、現在追跡されている番号と部分的に重複する間隔を追加すると、まだ追跡されていない番号が間隔に追加されるはずです。
• queryRange（left、right）。これは、間隔[左、右）のすべての実数が現在追跡されているときにtrueを返します。
• removeRange（left、right）、これにより、間隔[left、right）で現在追跡されているすべての実数の追跡が停止します。

これを解決するには、次の手順に従います-

• 1つのマップを定義するm
• 関数addRange（）を定義します。これは、左、右になります。
• removeRange（left、right）
• m [左]：=右
• it：=左がmにある場所
• mの最初の要素と等しくなく、前の要素の2番目の値が左と同じである場合、-
  • （1つ減らします）
  • 2番目：=正しい
  • mから左を削除
• mの最後の要素の前と等しくなく、次の最初の要素が右と同じである場合、-
  • その2番目：=次の2番目（それ）
  • mからnext（it）を削除
• 関数queryRange（）を定義します。これは、左、右になります。
• it：=mのサブパートの場所はすべて左よりも小さい値です
• mが空であるか、mの最初の要素と同じである場合、-
  • falseを返す
• （1つ減らします）
• 2番目のときにtrueを返す>=右
• 関数removeRange（）を定義します。これは、左、右になります。
• mが空の場合、-
  • 戻る
• it：=mのサブパートの位置すべて左より上の値
• mの最初の要素と等しくない場合、-
  • （1つ減らします）
• 配列を定義するv
• while（mの最後の要素とその最初の要素
• 最初の<左と2番目の>左の場合、-
  • temp：=2番目の
  • 2番目：=左
  • temp> rightの場合、m [right]：=temp
• それ以外の場合、最初の場合> =左、次に-
  • vの最後に最初に挿入します
  • その2番目が正しい場合>正しい場合、-
    • m [right]：=2番目の
• （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