Range xor queries with subarray reversals

// Implicit treap with lazy reversal.
// Supports O(log n): point update, range XOR query, range reversal.
// Reversal changes the index mapping for subsequent updates, so we cannot
// ignore it — we must track the full logical array order in the treap.
struct ImplicitTreap {
  lc: Vec<usize>,
  rc: Vec<usize>,
  pri: Vec<u32>,
  val: Vec<i32>,
  xsum: Vec<i32>,
  sz: Vec<usize>,
  rev: Vec<bool>,
  rng: u32,
  next: usize,
}

impl ImplicitTreap {
  fn new(n: usize) -> Self {
    let cap = n + 2;
    ImplicitTreap {
      lc: vec![0; cap],
      rc: vec![0; cap],
      pri: vec![0; cap],
      val: vec![0; cap],
      xsum: vec![0; cap],
      sz: vec![0; cap],
      rev: vec![false; cap],
      rng: 1_234_567_891,
      next: 1,
    }
  }

  fn rand(&mut self) -> u32 {
    self.rng ^= self.rng << 13;
    self.rng ^= self.rng >> 17;
    self.rng ^= self.rng << 5;
    self.rng
  }

  fn alloc(&mut self, v: i32) -> usize {
    let idx = self.next;
    self.next += 1;
    self.val[idx] = v;
    self.xsum[idx] = v;
    self.sz[idx] = 1;
    self.pri[idx] = self.rand();
    idx
  }

  fn update(&mut self, t: usize) {
    if t == 0 {
      return;
    }
    let (l, r) = (self.lc[t], self.rc[t]);
    self.sz[t] = 1 + self.sz[l] + self.sz[r];
    self.xsum[t] = self.val[t] ^ self.xsum[l] ^ self.xsum[r];
  }

  fn push_down(&mut self, t: usize) {
    if t == 0 || !self.rev[t] {
      return;
    }
    let (l, r) = (self.lc[t], self.rc[t]);
    self.lc[t] = r;
    self.rc[t] = l;
    if l != 0 {
      self.rev[l] ^= true;
    }
    if r != 0 {
      self.rev[r] ^= true;
    }
    self.rev[t] = false;
  }

  // Split into (first k elements, rest).
  fn split(&mut self, t: usize, k: usize) -> (usize, usize) {
    if t == 0 {
      return (0, 0);
    }
    self.push_down(t);
    let ls = self.sz[self.lc[t]];
    if ls >= k {
      let lc = self.lc[t];
      let (ll, lr) = self.split(lc, k);
      self.lc[t] = lr;
      self.update(t);
      (ll, t)
    } else {
      let rc = self.rc[t];
      let (rl, rr) = self.split(rc, k - ls - 1);
      self.rc[t] = rl;
      self.update(t);
      (t, rr)
    }
  }

  fn merge(&mut self, l: usize, r: usize) -> usize {
    if l == 0 {
      return r;
    }
    if r == 0 {
      return l;
    }
    self.push_down(l);
    self.push_down(r);
    if self.pri[l] > self.pri[r] {
      let rc = self.rc[l];
      let m = self.merge(rc, r);
      self.rc[l] = m;
      self.update(l);
      l
    } else {
      let lc = self.lc[r];
      let m = self.merge(l, lc);
      self.lc[r] = m;
      self.update(r);
      r
    }
  }

  fn range_xor(&mut self, root: &mut usize, l: usize, r: usize) -> i32 {
    let (left, mr) = self.split(*root, l);
    let (mid, right) = self.split(mr, r - l + 1);
    let result = self.xsum[mid];
    let mr = self.merge(mid, right);
    *root = self.merge(left, mr);
    result
  }

  fn range_reverse(&mut self, root: &mut usize, l: usize, r: usize) {
    let (left, mr) = self.split(*root, l);
    let (mid, right) = self.split(mr, r - l + 1);
    if mid != 0 {
      self.rev[mid] ^= true;
    }
    let mr = self.merge(mid, right);
    *root = self.merge(left, mr);
  }

  fn point_update(&mut self, root: &mut usize, idx: usize, new_val: i32) {
    let (left, mr) = self.split(*root, idx);
    let (node, right) = self.split(mr, 1);
    if node != 0 {
      self.val[node] = new_val;
      self.xsum[node] = new_val; // leaf: lc == rc == 0
    }
    let mr = self.merge(node, right);
    *root = self.merge(left, mr);
  }
}

impl Solution {
  pub fn get_results(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let mut treap = ImplicitTreap::new(n);
    let mut root = 0usize;

    for &v in &nums {
      let node = treap.alloc(v);
      root = treap.merge(root, node);
    }

    let mut results = Vec::new();

    for q in &queries {
      match q[0] {
        1 => treap.point_update(&mut root, q[1] as usize, q[2]),
        2 => results.push(treap.range_xor(&mut root, q[1] as usize, q[2] as usize)),
        3 => treap.range_reverse(&mut root, q[1] as usize, q[2] as usize),
        _ => {}
      }
    }

    results
  }
}