Maximum area rectangle with point constraints ii

impl Solution {
  pub fn max_rectangle_area(x_coord: Vec<i32>, y_coord: Vec<i32>) -> i64 {
    // O(n log^2 n) approach:
    // 1. Coordinate-compress y values.
    // 2. Build a merge-sort tree (segment tree on compressed y, each node holds a
    //    sorted list of x values).  This lets us answer "does any point exist with
    //    y ∈ [y1,y2] and x ∈ (x1,x2)?" in O(log^2 n).
    // 3. Sweep columns left→right.  For each consecutive (y1,y2) pair in the
    //    current column, if the same pair appeared earlier at x_prev, use the
    //    merge-sort tree to validate the candidate rectangle in O(log^2 n).
    //    Consecutive pairs guarantee the left/right borders are clear; we only
    //    need to reject rectangles that have an alien point inside or on the
    //    top/bottom edges between x_prev and x_curr.

    use std::collections::{BTreeMap, HashMap};

    let n = x_coord.len();
    if n < 4 {
      return -1;
    }

    // ── Coordinate-compress y ────────────────────────────────────────────────
    let mut ys_sorted: Vec<i32> = y_coord.clone();
    ys_sorted.sort_unstable();
    ys_sorted.dedup();
    let m = ys_sorted.len();
    let compress_y = |y: i32| -> usize { ys_sorted.partition_point(|&v| v < y) };

    // ── Build merge-sort tree ─────────────────────────────────────────────────
    // Each leaf cy holds the sorted x-values of all points with that compressed y.
    // Internal nodes store the merge of their children.
    let mut by_cy: Vec<Vec<i32>> = vec![Vec::new(); m];
    for i in 0..n {
      by_cy[compress_y(y_coord[i])].push(x_coord[i]);
    }
    for v in by_cy.iter_mut() {
      v.sort_unstable();
    }

    let mut tree: Vec<Vec<i32>> = vec![Vec::new(); 4 * m + 4];
    Self::build_tree(&mut tree, &by_cy, 1, 0, m - 1);

    // ── Sweep columns ─────────────────────────────────────────────────────────
    let mut by_x: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    for i in 0..n {
      by_x.entry(x_coord[i]).or_default().push(y_coord[i]);
    }
    for v in by_x.values_mut() {
      v.sort_unstable();
    }

    // Maps segment (y1,y2) → most-recent x where this consecutive pair appeared.
    let mut seg_prev_x: HashMap<(i32, i32), i32> = HashMap::new();
    let mut ans: i64 = -1;

    for (&x2, ys) in &by_x {
      for w in ys.windows(2) {
        let (y1, y2) = (w[0], w[1]);
        if let Some(&x1) = seg_prev_x.get(&(y1, y2)) {
          // All 4 corners exist.  Reject if any point lies with
          // x ∈ (x1,x2) and y ∈ [y1,y2].
          let cy1 = compress_y(y1);
          let cy2 = compress_y(y2);
          if !Self::has_point(&tree, 1, 0, m - 1, cy1, cy2, x1, x2) {
            let area = (x2 - x1) as i64 * (y2 - y1) as i64;
            if area > ans {
              ans = area;
            }
          }
        }
        seg_prev_x.insert((y1, y2), x2);
      }
    }

    ans
  }

  // ── Merge-sort tree helpers ───────────────────────────────────────────────────

  fn build_tree(
    tree: &mut Vec<Vec<i32>>,
    by_cy: &[Vec<i32>],
    node: usize,
    lo: usize,
    hi: usize,
  ) {
    if lo == hi {
      tree[node] = by_cy[lo].clone();
      return;
    }
    let mid = (lo + hi) / 2;
    Self::build_tree(tree, by_cy, 2 * node, lo, mid);
    Self::build_tree(tree, by_cy, 2 * node + 1, mid + 1, hi);
    let (l, r) = (tree[2 * node].clone(), tree[2 * node + 1].clone());
    tree[node] = Self::merge_sorted(&l, &r);
  }

  fn merge_sorted(a: &[i32], b: &[i32]) -> Vec<i32> {
    let mut out = Vec::with_capacity(a.len() + b.len());
    let (mut i, mut j) = (0, 0);
    while i < a.len() && j < b.len() {
      if a[i] <= b[j] {
        out.push(a[i]);
        i += 1;
      } else {
        out.push(b[j]);
        j += 1;
      }
    }
    out.extend_from_slice(&a[i..]);
    out.extend_from_slice(&b[j..]);
    out
  }

  /// Returns true if any stored point has compressed-y ∈ [ql,qr] and x ∈ (x1,x2).
  fn has_point(
    tree: &[Vec<i32>],
    node: usize,
    lo: usize,
    hi: usize,
    ql: usize,
    qr: usize,
    x1: i32,
    x2: i32,
  ) -> bool {
    if ql > hi || qr < lo {
      return false;
    }
    if ql <= lo && hi <= qr {
      // Binary-search for any x strictly in (x1, x2).
      let lo_idx = tree[node].partition_point(|&v| v <= x1);
      let hi_idx = tree[node].partition_point(|&v| v < x2);
      return lo_idx < hi_idx;
    }
    let mid = (lo + hi) / 2;
    Self::has_point(tree, 2 * node, lo, mid, ql, qr, x1, x2)
      || Self::has_point(tree, 2 * node + 1, mid + 1, hi, ql, qr, x1, x2)
  }
}