Skip to content

Willem, Chtholly and Seniorious

Why It Fits This Lane

This is the canonical Chtholly Tree problem.

The whole route is exactly:

  • keep the array as one ordered set of disjoint constant intervals
  • use split(l) and split(r + 1) before every range touch
  • let assign(l, r, x) collapse many current intervals into one
  • walk the current slice for add, kth, and power-sum queries

It is also the place where the usual honesty warning matters most:

  • the route works because the data is generator-driven and intentionally soft
  • it is not a universal worst-case guarantee

Problem Restatement

You are given:

  • array length n
  • number of generated operations m
  • one seed and one vmax

The initial array and every future query are generated by the provided pseudo-random generator.

Operations are:

  1. add x to every value in [l, r]
  2. assign every value in [l, r] to x
  3. return the x-th smallest value in [l, r]
  4. return \(\sum a_i^x \bmod y\) over [l, r]

The task is to print the answers for operations 3 and 4.

The Model

The wrong first instinct is:

  • store the whole array
  • update every position directly
  • sort the whole range for every k-th query

That is too slow.

The right model is:

  • each node stores one interval [l, r] with one constant value v
  • the set is ordered by l
  • every range operation first isolates its boundaries with split

After that:

  • assign erases the whole interval slice and inserts one new node
  • add walks the slice and increases each touched node's value
  • kth collects (value, length) pairs from the slice and sorts them
  • power-sum walks the slice and accumulates length * value^x mod y

Exact Route Used Here

This repo keeps the route narrow and explicit:

  • std::set<Node> with nodes [l, r, v]
  • split(pos) on the left endpoint order
  • assign(l, r, value) as the interval-collapsing primitive
  • honest interval walks for the other operations

The exact complexity is driven by the number of touched segments, not by a fake blanket O(log n) claim.

Why This Passes Here

The operation that keeps the structure healthy is:

assign(l, r, x)

because it collapses the whole touched slice back into one interval.

Together with the generator-driven data, this keeps the number of intervals manageable in practice, which is exactly the environment where ODT belongs.

Implementation Sketch

Maintain:

  • set<Node> odt
  • split(pos)
  • assign_range(l, r, value)
  • add_range(l, r, delta)
  • kth_smallest(l, r, k)
  • range_pow_sum(l, r, exp, mod)

For every generated query:

  1. produce op, l, r, x, y from the generator
  2. isolate [l, r] with split
  3. apply the operation on the current interval slice

Repo Route

Solution

Reference implementation:

Stretch

After this rep, a good deterministic bridge is:

and a good compare point is:

because it shows exactly when hard online guarantees matter more than short interval-partition code.