The transition often has structure that allows further improvement with Convex Hull Trick (covered in Section ).
If can be written as (separable into terms depending only on and terms depending only on ), CHT applies. Each transition becomes a line query.
This problem achieves by combining Aliens Trick with CHT. First Aliens removes the dimension, then CHT speeds up the transitions to . The techniques compose beautifully.