Handling the addition of a catgirl

When adding a new catgirl, there are 2 possible cases for an optimal image, either the new catgirl is included in the photo or she isn't.

In the case that the optimal photo includes the newly added catgirl, the rightmost catgirl in the photo should be the newly added catgirl.

We can use binary search to find the leftmost possible catgirl in the image such that it fits in the field of view, using prefix sum arrays to efficiently calculate the sum of the pose widths.

After finding the leftmost possible catgirl that fits in the field of view of your camera, you can calculate the sum of the cutenesses using a prefix sum array.

The maximum cuteness is either the cuteness of the photo including the new catgirl or the cuteness from the last step (excluding the new catgirl).

Handling the deletion of a catgirl

Whenever a catgirl leaves the line, the state of the line reverts back to a previous state. These previous states can be stored in a stack to avoid re-computation.

When a catgirl leaves the line, the last element in the stack can be removed, as well as the last element in the cuteness and pose width prefix sum arrays.

Time complexity: ~\mathcal{O}(N \log N)~