Subtask 1

For each pair of horizontal lines, we can find the number of pairs of vertical lines that intersect both horizontal lines by looping through all vertical lines in order of their x-axis.

Time Complexity: ~\mathcal{O}(H^2 V + V \log V)~

Subtask 2

For full marks, we need a faster way to query the number of rectangles. One possible solution is described here. For each horizontal line ~i~, find any vertical lines that intersect ~i~ and insert them into a BIT. Then, run line sweep descending the y-axis. When we reach the endpoint of a vertical line that intersected ~i~, remove it from the BIT. When we reach another horizontal line ~j~, query the union of the two horizontal lines to get the number of vertical lines that intersect both ~i~ and ~j~. To exclude rectangles with an area of ~0~, we maintain a frequency array and another BIT to keep track of the number of pairs of overlapping vertical lines on each x-coordinate. A well implemented solution should pass comfortably under the time limit.

Time Complexity: ~\mathcal{O}(H (H+V) \log(H+V))~