Here the coordinates are relatively small therefore we will compute for each coordinate (x,y) the number l(x,y) of layers at that position. To do that efficiently, we use the same trick as in the prefix sum but in reverse, when adding a rectangle (x1,y1,x2,y2) l(x,y) is: - increased by one if x ≥ x1 and y ≥ y1 - further reduced by one if x > x2 and y ≥ y1 - further reduced by one if x ≥ x1 and y > y2 - further increased by one if x > x2 and y > y2 Therefore we can maintain an array p[x][y] such that l(x,y) = Σ_{x'≤x, y'≤y} p[y'][x'] under the addition of rectangles of paint. Once we have compute p we can recover l(x,y) with l(x-1,y)+l(x,y-1)-l(x-1,y-1)+p[y][x]