The challenge
'a[i] = min(a[i], x)' can't be pushed lazily — depends on each value. Naive: O(N log N) per op.
Advertisement
The trick
Each node stores max, second-max, count of max. If x ≥ second-max, update is 'clamp maxes to x' — pushable.
Advertisement
Complexity
Amortized O(log² N) per op. Analysis is subtle — involves total number of distinct maxes across tree.
Applications
Competitive programming. Sequences with range clamp + aggregate queries.