Paint and Sum — Solution & Editorial

Back to the Problem

A segment tree with a lazy 'assign' tag (distinct from lazy add): pushing an assignment overwrites a subtree's sum to v×length. (An interval set / Chtholly tree also works when assignments dominate.)

Complexity: O((N + Q) log N)

Watch out: Assignment lazy tags overwrite (not accumulate) — mixing them with add tags requires careful ordering.