MO's Optimization - Zigzag Order

The standard MO sorting has a hidden inefficiency. When moving to a new $l$-block, $r$ might jump from high to low, causing $O(n)$ movement.

Fix: alternate sorting direction of $r$ for odd vs even $l$-blocks. pseudocode sort queries by: primary key: floor(l / B) secondary key: r if block is even, else -r This zigzag pattern makes $r$ sweep back and forth instead of jumping.

In practice, this can speed up MO's algorithm by $2\times$ or more. The total complexity is still $O((n + q)\sqrt{n})$, but the constant factor drops by roughly half. Time: $O((n + q)\sqrt{n})$. Space: $O(n)$.