In the past we had indexed color screen modes. You could draw all pixels to the screen once and give each pixel an index into a color palette. When you would start, they would all be mapped to white, but as you start with coloring, you would then just change the color of the palette entry (truly a O(1) operation) and your graphics card would then do the work at scan time. I guess the closest equivalent nowadays would be to do this inside the pixel shader.