Crystal List: Editorial¶
Solutions and tradeoffs¶
Problem setter’s solution: a uniform-type segment tree. The uniform-type segment tree is the preferred method. An ordered interval map directly represents equal-type runs and provides an alternative with the same asymptotic amortized bounds. Segment-tree construction must handle an empty sequence separately instead of recursing on an empty interval.
Programs and credits: std.cpp implements the problem setter’s solution; Codex (GPT-6) contributed implementation details, boundary handling and proof exposition. For the ordered interval map method used by Codex (GPT-6), see alternative.cpp and the alternative editorial.
Segment tree with uniform-type tags¶
Build a segment tree over positions. Each node either records one type for its entire segment or is marked mixed. Type energies live in a separate array, so an energy update changes only one array entry. When a replacement fully covers a uniform node, its score is the segment length times the absolute energy difference between the old and new types; the node then receives the new type. Mixed or partially covered nodes recurse into their children, pushing uniform tags when needed. On return, children with equal types are merged into a uniform parent.
Every position in a uniform node contributes the same amount, and its children partition the segment, so this computes exactly the score of individual replacements. Tags represent types, and replacement still changes a type when the two energies are equal.
An individual replacement can visit more than logarithmically many nodes, but the method has a deterministic amortized bound. Count only active mixed nodes, excluding descendants hidden by a uniform ancestor tag. Initially there are \(O(n)\) such nodes. One operation can create new mixed nodes only at the \(O(\log(n+2))\) nodes near its two boundaries. Every fully covered mixed node that is expanded becomes uniform afterward, so that traversal is charged to a disappearing mixed node. Total time is therefore \(O(n+k+m\log(n+2))\) and space is \(O(n+k)\) , where \(n\) is the number of positions, \(k\) the number of types and \(m\) the number of operations.
Implementation boundaries¶
Types start at one; zero denotes a mixed node. Pushing a uniform tag overwrites both children, and a parent becomes uniform only when its children have the same type. Energy changes update the lookup array without traversing the tree.
Skip construction when \(n=0\) ; valid input then contains no interval replacements. When \(k=0\) , no energy update occurs either. A score is at most \(49999n\) , so products and totals use 64-bit integers. Equal-energy but distinct types must still be replaced because future energy updates can distinguish them.
Validation and performance¶
Timing and peak-memory measurements are available in environment and measurements.