Beats And Second Maximum

Segment tree beats supports range chmin alongside range sum. What tag does each node keep, and where does the recursion stop?

Maximum, a lazy add tag, and the count of maxima. chmin(l,r,x) stops when $x \ge \max$ (nothing changes) or when the node is fully covered (the tag absorbs it, so the sum shifts by $len \cdot (x - \max)$ ). It recurses only when it is partly covered, which makes it $O(\log n)$ worst case.

Maximum, strict second maximum, and the count of maxima. chmin(l,r,x) stops when $x \ge \max$ (nothing changes) or when $secondmax < x < \max$ (only the maxima move, so the sum shifts by $cnt \cdot (x - \max)$ ). It recurses only when $x \le secondmax$ .

Maximum, minimum, and the count of maxima. chmin(l,r,x) stops when $x \ge \max$ (nothing changes) or when $\min < x < \max$ (only the maxima move, so the sum shifts by $cnt \cdot (x - \max)$ ). It recurses only when $x \le \min$ .

Maximum, strict second maximum, and the count of maxima. chmin(l,r,x) stops when $x \le \max$ (nothing changes) or when $secondmax < x < \max$ (all elements move, so the sum shifts by $len \cdot (x - \max)$ ). It recurses only when $x \ge secondmax$ .