โมดูลช่วงใน C ++

สมมติว่าเราต้องการโมดูลช่วง นี่คือโมดูลที่ติดตามช่วงของตัวเลข งานของเราคือการออกแบบและใช้งานอินเทอร์เฟซต่อไปนี้อย่างมีประสิทธิภาพ

• addRange (ซ้าย, ขวา) นี่จะเป็นช่วงครึ่งเปิด [ซ้าย, ขวา) ติดตามทุกจำนวนจริงในช่วงเวลานั้น ตอนนี้ การเพิ่มช่วงเวลาที่ทับซ้อนกับตัวเลขที่ติดตามอยู่บางส่วนควรเพิ่มตัวเลขใดๆ ในช่วงที่ยังไม่ได้ติดตาม
• queryRange(ซ้าย ขวา) ค่านี้จะคืนค่าเป็นจริงเมื่อทุกจำนวนจริงในช่วงเวลา [ซ้าย, ขวา) กำลังถูกติดตาม
• removeRange(ซ้าย, ขวา) การดำเนินการนี้จะหยุดติดตามทุกจำนวนจริงที่กำลังถูกติดตามในช่วงเวลา [ซ้าย, ขวา)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งแผนที่ m
• กำหนดฟังก์ชัน addRange() ซึ่งจะใช้ซ้าย ขวา
• removeRange(ซ้าย,ขวา)
• ม[ซ้าย] :=ขวา
• มัน :=ตำแหน่งที่ด้านซ้ายมีอยู่ใน m
• ถ้ามันไม่เท่ากับองค์ประกอบแรกของ m และค่าที่สองของค่าก่อนหน้ามันเหมือนกับด้านซ้าย ดังนั้น −
  • (ลดลง 1)
  • วินาทีนั้น :=ขวา
  • ลบด้านซ้ายจาก m
• ถ้าไม่เท่ากับส่วนก่อนหน้าขององค์ประกอบสุดท้ายของ m และตัวแรกของตัวถัดไปเท่ากับด้านขวา −
  • วินาที :=วินาทีถัดไป(มัน)
  • ลบ next(it) จาก m
• กำหนดฟังก์ชัน queryRange() ซึ่งจะใช้ซ้าย ขวา
• มัน :=ตำแหน่งของส่วนย่อยของ m ที่มีค่าน้อยกว่าด้านซ้ายทั้งหมด
• ถ้า m ว่างเปล่าหรือเหมือนกับองค์ประกอบแรกของ m แล้ว −
  • คืนค่าเท็จ
• (ลดลง 1)
• คืนค่า จริง เมื่อวินาทีของมัน>=ถูกต้อง
• กำหนดฟังก์ชัน removeRange() ซึ่งจะใช้ซ้าย ขวา
• ถ้า m ว่างเปล่า ดังนั้น −
  • คืนสินค้า
• มัน :=ตำแหน่งของส่วนย่อยของ m ค่าบนทั้งหมดมากกว่าด้านซ้าย
• ถ้ามันไม่เท่ากับองค์ประกอบแรกของ m แล้ว −
  • (ลดลง 1)
• กำหนดอาร์เรย์ v
• ในขณะที่ (ไม่เท่ากับองค์ประกอบสุดท้ายของ m และตัวแรก
• ถ้าอย่างแรก <ซ้ายและอันที่สอง> ซ้าย แล้ว −
  • อุณหภูมิ :=วินาทีนั้น
  • วินาทีนั้น :=ซ้าย
  • ถ้า temp> ถูก แล้ว: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