A dispatch report asks four unrelated questions over numbered observations. Which nonnegative code is absent from a historical range? What is the greatest XOR achievable by a subset of shipment flags? What is a corrected sensor sum after overlapping multiply-and-add calibrations? Which current dispatch job has the lowest or highest priority? Use a persistent last-occurrence index, a segment tree of binary linear bases, an affine lazy segment tree, and a min-max heap respectively. Keep each result's domain and update policy separate: the first array is immutable, the XOR tree replaces points, the calibration tree transforms ranges under one modulus, and the heap mutates by inserting or removing its extremes.
Make this comfortable
Project: audit range MEX, XOR spans, calibration sums, and priority ends
Acceptance trace
For [0,3,1,0,2,7,1], require MEX four on [0,5) and three on [2,7). On flags [47,29,61,83,19], require maximum subset XOR 115 for [1,4), then replace 61 with 37 and require 118. On readings [47,19,61,29,83] modulo 1009, apply x maps to 3x+7 over [1,4), then x maps to 2x+5 over [2,5), and require total 860. Finally insert seven dispatch priorities with both 47 values retained; pop 19 and 83 and require 29 and 61 as the remaining endpoints. Compare every result with direct enumeration or arithmetic before accepting the index output.
Failure and cost review
Test empty and single-item MEX windows and confirm an earlier root does not change after later prefix versions are built. For short XOR ranges, enumerate all subsets and compare both maximum and representability, including duplicate and zero flags. Compose affine updates in both orders on an overlapping region to prove order matters; test multiplier zero as assignment. Mix heap insertion with both endpoint removals and compare its multiset with a sorted list after every operation. Record the range query costs separately rather than claiming one universal logarithmic index. Reject unsupported point edits to the frozen MEX array and out-of-width XOR flags.
Common Mistakes
- Do not query a MEX from the wrong prefix version.
- Do not count a dependent XOR vector as a new pivot.
- Do not reverse affine composition over an overlap.
- Do not treat min-max heap positions as stable job handles.
Connected lessons
data structures
projects