Subtask 1

Iterate through every line and check if it intersects with any other line by iterating through all points in one and checking if it overlaps with the other line.

Time Complexity: ~\mathcal{O}(N^{2}(\sum_{i=1}^{N} x_{2_{i}} - x_{1_{i}} + y_{2_{i}} - y_{1_{i}}))~

Subtask 2

Maintain two grids: one that counts the number of horizontal lines at a given point and the other for the number of vertical lines.

Iterate through the grid and sum the number of horizontal lines multiplied by the number of vertical lines at any given point.

Time Complexity: ~\mathcal{O}((\max(x_{2_{i}}) - \min(x_{1_{i}})) \times (\max(y_{2_{i}}) - \min(y_{1_{i}})))~

Subtask 3

Perform a line sweep on the x-coordinate of the start and end points of horizontal lines and the x-coordinate of the vertical lines.

Maintain a data structure (e.g. segment tree or Fenwick tree) that can support point-update and range queries.

First, perform coordinate compression on the x-coordinates and y-coordinates to support them in your data structure (or use an implicit segment tree).

When you encounter the start point of a horizontal line, add ~1~ to the frequency at the y-coordinate in the data structure.

When you encounter the end point of a horizontal line, subtract ~1~ to the frequency at the y-coordinate in the data structure.

When you encounter a vertical line, query the sum of lines in ~[y_{1_{i}}, y_{2_{i}}]~ in the data structure.

Note that you should be cautious of the order you process the lines: break ties in x-coordinates based on the type with start points of horizontal lines first, vertical lines, and finally, end points of horizontal lines.

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