Path existence queries in a graph ii

impl Solution {
  pub fn path_existence_queries(
    n: i32,
    nums: Vec<i32>,
    max_diff: i32,
    queries: Vec<Vec<i32>>,
  ) -> Vec<i32> {
    let n = n as usize;
    // Sort nodes by value
    let mut order: Vec<usize> = (0..n).collect();
    order.sort_unstable_by_key(|&i| nums[i]);

    // sorted_pos[i] = position of node i in the sorted order
    let mut sorted_pos = vec![0usize; n];
    for (p, &node) in order.iter().enumerate() {
      sorted_pos[node] = p;
    }

    // In sorted order, nodes p and p+1 are connected iff
    // nums[order[p+1]] - nums[order[p]] <= maxDiff
    // Connected components in sorted order are contiguous ranges
    // comp[p] = component id of node at sorted position p
    let mut comp = vec![0u32; n];
    let mut cur = 0u32;
    for p in 1..n {
      if nums[order[p]] - nums[order[p - 1]] > max_diff {
        cur += 1;
      }
      comp[p] = cur;
    }

    // For BFS distance: nodes in same component form a clique-like structure in sorted-value space
    // The minimum distance between two nodes u, v (same component):
    // In the sorted order they are at positions pu and pv.
    // The shortest path length = distance in the "path graph" on sorted positions
    // where edge exists between p and q if |sorted_vals[p] - sorted_vals[q]| <= maxDiff.
    // This is equivalent to: the min number of hops in interval graph of sorted values.
    // 
    // Use binary lifting on sorted positions within each component.
    // jump[k][p] = the furthest sorted position reachable from p in 2^k hops
    // One hop from position p: can reach any q s.t. nums[order[q]] - nums[order[p]] <= maxDiff
    //   (going right) or nums[order[p]] - nums[order[q]] <= maxDiff (going left)
    // But nums is sorted by the sort order, so from sorted position p:
    //   rightmost reachable = last position where sorted_val <= sorted_val[p] + maxDiff
    //   leftmost reachable = first position where sorted_val >= sorted_val[p] - maxDiff
    
    let sorted_vals: Vec<i32> = order.iter().map(|&i| nums[i]).collect();

    let log = 17usize;
    // jump_r[k][p] = furthest right position reachable from p in 2^k hops
    // jump_l[k][p] = leftmost left position reachable from p in 2^k hops
    let mut jump_r = vec![vec![0usize; n]; log];
    let mut jump_l = vec![vec![0usize; n]; log];

    // Base: 1 hop
    for p in 0..n {
      // rightmost reachable: binary search for last q with sorted_vals[q] <= sorted_vals[p] + maxDiff
      let target = sorted_vals[p] + max_diff;
      let r = sorted_vals.partition_point(|&v| v <= target).saturating_sub(1);
      jump_r[0][p] = r;
      // leftmost reachable: binary search for first q with sorted_vals[q] >= sorted_vals[p] - maxDiff
      let target_l = sorted_vals[p] - max_diff;
      let l = sorted_vals.partition_point(|&v| v < target_l);
      jump_l[0][p] = l;
    }

    // Fill binary lifting
    for k in 1..log {
      for p in 0..n {
        let r1 = jump_r[k - 1][p];
        jump_r[k][p] = jump_r[k - 1][r1];
        let l1 = jump_l[k - 1][p];
        jump_l[k][p] = jump_l[k - 1][l1];
      }
    }

    // Distance from sorted pos pu to pv (pu <= pv): 
    // use binary lifting to find min hops to "cover" the gap
    let dist = |pu: usize, pv: usize| -> i32 {
      if pu == pv { return 0; }
      if comp[pu] != comp[pv] { return -1; }
      // pu < pv: count hops going right
      let mut pos = pu;
      let mut hops = 0i32;
      for k in (0..log).rev() {
        if jump_r[k][pos] < pv {
          pos = jump_r[k][pos];
          hops += 1 << k;
        }
      }
      // one more hop to reach pv
      if jump_r[0][pos] >= pv {
        hops + 1
      } else {
        -1
      }
    };

    queries
      .iter()
      .map(|q| {
        let u = q[0] as usize;
        let v = q[1] as usize;
        let pu = sorted_pos[u];
        let pv = sorted_pos[v];
        if pu <= pv {
          dist(pu, pv)
        } else {
          dist(pv, pu)
        }
      })
      .collect()
  }
}