vi. Chtholly Tree (Interval Map)

Store the array as maximal runs of equal values in an ordered map. Range assign collapses many runs into one. Any range operation then visits the runs it covers. It’s also called ODT (“old driver tree”) after CF 896C.

Implementation

template<class T> struct IntervalMap {
    map<ll, T> m;                                  // run start -> value; key hi is a sentinel
    IntervalMap(ll lo, ll hi, T init) { m[lo] = init; m[hi] = init; }
    auto split(ll x) {                             // make x the start of a run
        auto it = prev(m.upper_bound(x));
        return it->first == x ? it : m.emplace_hint(next(it), x, it->second);
    }
    void assign(ll l, ll r, T v) {                 // a[l, r) = v
        auto ir = split(r), il = split(l);
        m.erase(next(il), ir); il->second = v;
    }
    template<class F> void each(ll l, ll r, F f) { // f(start, end, value&) for every run in [l, r)
        auto ir = split(r), il = split(l);
        for (auto it = il; it != ir; ++it) f(it->first, next(it)->first, it->second);
    }
};

Split $r$ before $l$. With this map + emplace_hint version either order works, because splitting never erases a node. In the common set<Node> implementation, splitting re-inserts a run, so splitting $l$ first can invalidate the iterator for the run containing $r$.

Complexity

Each assign removes all runs inside it and adds at most 3, so the number of runs created overall is $O(n+q)$, and assign is $O(\log n)$ amortized. The cost of each is proportional to the number of runs visited.

Proof: assign is $O(\log n)$ amortized, and total each/assign work across runs is $O(n+q)$

Use the potential $\Phi =$ (current number of runs in the map). split(l) and split(r) each add at most one new run (splitting one run into two), so one assign call increases $\Phi$ by at most 2 from splitting, then deletes every run strictly between the split points and inserts one run for $[l,r)$ — a net change that is bounded (deleting $k$ runs and adding $1$ changes $\Phi$ by $1-k\le 1$). So each assign increases $\Phi$ by at most $O(1)$ (from the two splits) while the map operations themselves (the two splits, $O(\log n)$ each, plus erasing $k$ runs, $O(k\log n)$) cost $O(\log n)$ for the splits and $O(k\log n)$ for the erase. Since $\Phi$ starts at $O(1)$, is increased by $O(1)$ per assign, and every unit of $\Phi$ erased was created by some earlier split/assign, the total number of runs ever created over $q$ queries on an array that started with $O(n)$ runs is $O(n+q)$ — each creation charged $O(\log n)$ to insert and $O(\log n)$ to eventually erase, so total map-maintenance work is $O((n+q)\log n)$, i.e. $O(\log n)$ amortized per assign. Any call to each (or the erase loop inside assign) visits only runs that exist right now, and every run it visits either survives (bounded total existence) or gets deleted (charged once, as above) — so the total work across all each/assign calls visiting runs is also $O(n+q)$. $■$

• With random operations where a constant fraction are assigns (CF 896C), the expected number of runs stays $O(\log n)$-ish and every operation is fast.
• Adversarial tests with few assigns make each $O(n)$ per call. Then you need a real structure (lazy segment tree, segment tree beats).

Where it is the intended or best tool

• Range assign + anything weird on the runs: $k$-th smallest in a range (collect runs, sort), sum of $x$-th powers mod $y$ in a range (per run: pow(value, x) * length). These are the CF 896C operations.
• Union of intervals / painting: IntervalMap<bool>; total painted length via each.
• “Colour the range $[l,r]$ with $c$, report how many cells change colour”: count lengths of runs whose value differs from $c$ before assigning. Amortized $O((n+q)\log n)$ deterministically, because each assign removes the runs it counts.

Proof: the colour-change counting query is $O((n+q)\log n)$ total, deterministically

This is exactly each immediately followed by assign over the same range: the runs visited by each to count mismatched lengths are precisely the runs that assign’s erase loop is about to delete, so this operation never visits a run “for free” that it doesn’t also charge to a deletion. By the run-creation/deletion accounting above, every run deleted was created once (at a cost of $O(\log n)$) and is now being both counted and deleted (another $O(\log n)$), so this combined operation’s cost is exactly accounted for by the same $O(n+q)$-total-run-creations argument — no adversarial input can force more visits than runs ever created, unlike plain each alone (which, as the note says, can be forced to $O(n)$ repeatedly if assigns are rare, since nothing then deletes the runs being re-scanned). $■$

• Maintaining a set of disjoint intervals (merge on insert, split on delete), like “free memory blocks”, “covered positions”, or “segments of equal values with counts”.
• Amortized arguments on trees: the same idea along HLD chains (assign a colour to a root path, count colour changes) gives the classic $O({\log }^{2}n)$ amortized “access” analysis used in link-cut tree style problems.

A set<pair<ll,ll>> of disjoint intervals with the same split/merge discipline is the minimal version when there’s no value to store.