Range Module

struct RangeModule {
    covered: std::collections::BTreeSet<i32>,
}

impl RangeModule {
    fn new() -> Self { Self { covered: std::collections::BTreeSet::new() } }
    fn add_range(&mut self, left: i32, right: i32) {
        for x in left..right { self.covered.insert(x); }
    }
    fn query_range(&self, left: i32, right: i32) -> bool {
        (left..right).all(|x| self.covered.contains(&x))
    }
    fn remove_range(&mut self, left: i32, right: i32) {
        for x in left..right { self.covered.remove(&x); }
    }
}

class RangeModule {
  private covered = new Set<number>();
  addRange(l: number, r: number): void { for (let x = l; x < r; x++) this.covered.add(x); }
  queryRange(l: number, r: number): boolean {
    for (let x= l; x < r; x++) if (!this.covered.has(x)) return false;
    return true;
  }
  removeRange(l: number, r: number): void { for (let x= l; x < r; x++) this.covered.delete(x); }
}

use std::collections::BTreeMap;

struct RangeModule {
    intervals: BTreeMap<i32, i32>,
}

impl RangeModule {
    fn new() -> Self { Self { intervals: BTreeMap::new() } }

    fn add_range(&mut self, left: i32, right: i32) {
        let (mut lo, mut hi) = (left, right);
        let touching: Vec<i32> = self
            .intervals
            .range(..=hi)
            .filter(|(_, &e)| e >= lo)
            .map(|(&s, _)| s)
            .collect();
        for s in touching {
            let e = self.intervals.remove(&s).unwrap();
            if s < lo { lo= s; }
            if e > hi { hi = e; }
        }
        self.intervals.insert(lo, hi);
    }

    fn query_range(&self, left: i32, right: i32) -> bool {
        self.intervals
            .range(..=left)
            .next_back()
            .map_or(false, |(_, &e)| e >= right)
    }

    fn remove_range(&mut self, left: i32, right: i32) {
        let crossing: Vec<i32> = self
            .intervals
            .range(..right)
            .filter(|(_, &e)| e > left)
            .map(|(&s, _)| s)
            .collect();
        let mut to_insert: Vec<(i32, i32)> = Vec::new();
        for s in crossing {
            let e = self.intervals.remove(&s).unwrap();
            if s < left { to_insert.push((s, left)); }
            if e > right { to_insert.push((right, e)); }
        }
        for (s, e) in to_insert { self.intervals.insert(s, e); }
    }
}

// Simple sorted-array implementation. O(log n) via binary search for query;
// mutations walk a contiguous slice, so O(k) with amortized O(1) touched.
class RangeModule {
  private starts: number[] = [];
  private ends: number[] = [];

  private bisectRight(arr: number[], x: number): number {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] <= x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  addRange(left: number, right: number): void {
    let lo = left, hi = right;
    // Find first interval with start > hi; everything before may touch.
    const end = this.bisectRight(this.starts, hi);
    // Walk backwards from end - 1 while the interval touches.
    let removeLo = end, removeHi = end;
    for (let i = end - 1; i >= 0 && this.ends[i] >= lo; i--) {
      if (this.starts[i] < lo) lo = this.starts[i];
      if (this.ends[i] > hi) hi = this.ends[i];
      removeLo = i;
    }
    this.starts.splice(removeLo, removeHi - removeLo, lo);
    this.ends.splice(removeLo, removeHi - removeLo, hi);
  }

  queryRange(left: number, right: number): boolean {
    const i = this.bisectRight(this.starts, left) - 1;
    return i >= 0 && this.ends[i] >= right;
  }

  removeRange(left: number, right: number): void {
    const end = this.bisectRight(this.starts, right - 1);
    let start = end;
    while (start - 1 >= 0 && this.ends[start - 1] > left) start--;
    if (start === end) return;
    const chunkStarts = this.starts.splice(start, end - start);
    const chunkEnds = this.ends.splice(start, end - start);
    const replaceStarts: number[] = [];
    const replaceEnds: number[] = [];
    for (let i = 0; i < chunkStarts.length; i++) {
      if (chunkStarts[i] < left) {
        replaceStarts.push(chunkStarts[i]);
        replaceEnds.push(left);
      }
      if (chunkEnds[i] > right) {
        replaceStarts.push(right);
        replaceEnds.push(chunkEnds[i]);
      }
    }
    this.starts.splice(start, 0, ...replaceStarts);
    this.ends.splice(start, 0, ...replaceEnds);
  }
}