Lessons from Polynomial Queries

Important lessons:

$1.$ Lazy propagation works with sqrt decomposition too, not just segment trees

$2.$ For non-uniform updates, store the parameters needed to reconstruct the update pattern

$3.$ Pushdown is only needed for tails; complete blocks you can handle with formulas This problem shows that sqrt decomposition is more flexible than it first appears. With creativity, it handles complex update patterns.