Since every dish contains at most ~10^9~ cells, then, if we use the spray on it at least ~32~ times, it is guaranteed to become empty. Therefore, we could store answers to the question "what the sum on this segment would be after ~i~ applications of the spray" for \(0 \le i \le 32\) in every node of a segment tree.

There is another solution: using the same observation, we observe that, if we don't apply the spray to empty dishes, then, without any updates, we can have \(32 × N\) applications of the spray at most, and each update adds at most ~32~ additional applications. Therefore, we can actually apply the spray to dishes one-by-one, and the only problem is finding the non-empty dishes quickly, which is easily accomplished by a segment tree or a set.

This solution wouldn't work if we were allowed to update the number of cells in a segment of dishes at once, but it was easier to implement.