Let's construct the following graph: let each node be a rectangle from the task, and the edge between nodes ~A~ and ~B~ will exist if the rectangle represented by node ~A~ is the smallest rectangle that contains the rectangle represented by node ~B~. We can notice that the constructed graph is a forest of trees where the roots of the trees are rectangles that are not contained in any other rectangle. We can construct this graph using the sweep line algorithm. We scan on the ~x~-axis from ~0~ to ~+\infty~ and at the same time maintain the tournament tree on the ~y~-axis. When the imaginary scanning line reaches the left side of a rectangle, we insert its index into the tournament tree in the interval ~[b, d]~ (~b~ is the lower ~y~-coordinate, ~d~ is the upper). However, before inserting, we check to see in the tournament tree which rectangle currently covers that interval in order to construct an edge between them. When we reach the right side of a rectangle, we remove its index from the interval ~[b, d]~. The complexity of this part is ~\mathcal O(N \log N)~.

Now let's place each paintball ball in the node that corresponds to the smallest rectangle that contains that paintball ball. We can do this using an almost identical sweep line algorithm in the same complexity. Now we've reduced the task to calculating, for each node, the number of different paintball balls in its subtree. We can do this by traversing the nodes from the deepest to the root by using a DFS tree traversal, and for each node maintaining a set of all paintball balls that are in the current node's subtree. More precisely, when we're processing a node, we merge its set of paintball balls with the sets of its children. We need to make sure that, when merging the sets, we always merge the smaller set with the bigger one, so we don't end up with a bigger complexity of the operation. You can read more about this here. Finally, for each node, we output the size of its set.

The complexity of the second part is ~\mathcal O(N \log^2 N)~, which is also the total complexity of the algorithm. There is a solution of the complexity ~\mathcal O(N \log N)~, and it is left as an exercise to the reader.