Problem link : contest practice
Difficulty : Hard
Pre-requisites : 2D data structures, segment trees
Solution :
Let’s start with the following claim: two rectangles intersect if and only if their projections on the coordinate axes intersect. This is an observation that isn’t hard to come up with, and that can be easily reasoned.
Let’s consider the following problem, where we have to manage answering two types of queries:
- Add a segment, denoted by its’ endpoints x and y;
- Count the number of segments that intersect with the segment, denoted by the endpoints x and y.
This problem can be solved with the following approach:
- We keep track on the total number of the segments and all the leftmost and the rightmost endpoints of the segments. For these purposes, one can use segment tree;
- When we need to calculate the number of the segments that intersect with the given one (let’s denote its’ the leftmost and the rightmost endpoints by L and R respectively), we can simply subtract the number of the segments that don’t intersect with the given one from the total number of the segments. The number of the segments that don’t intersect with the given one is: the number of the segments with the leftmost coordinate greater than R plus the number of the segment with the rightmost coordinate smaller than L. Calculating the sought number of segments can be done now with a segment tree, that was already mentioned above.
How to calculate the number of the rectangles that don’t intersect with the given one (denoted by its’ projections Xl, Xr and Yl, Yr)? From the first glance, we might say that is: the total number of the rectangles, minus the number of rectangles with the X-axis projection, not intersecting [Xl, Xr], minus the number of rectangles with the Y-axis projection, not intersecting [Yl, Yr]. But this is wrong, because some of the rectangles might be subtracted twice. To be exact, those that don’t intersect with the both of the projections.
There are four symmetric cases for such rectangles. Let’s consider one of these cases, for example those when the both top/right most coordinates of the rectangle (and the projection respectively) are smaller than the bottom/left most coordinates of the rectangle (and the projection as well). Actually, we can simply calculate the number of such rectangles by counting the number of the rectangles with the top-right corner inside the rectangle (1, 1, Xl-1, Yl-1). So now the problem becomes a standard one and you only have to:
- Add a point on the plane;
- Calculate the number of the points inside the axes-parallel rectangle.
There are generally a lot of ways to do it. Take a look at the setter’s/tester’s solutions for the details in case you’re unfamiliar how to do so. Though, there are really a lot of ways, so everyone can find the most convenient one for himself. The tester prefers 2D Fenwick tree+SQRT decomposition. This approach is capable of achieving the maximal runtime of ~0.7 on the given test cases.
The described case is one of four, the rest has exactly the same logic. The main difficulty of the problem is to code everything clear and correct, but only the practice helps to become stronger in the “techical” problems 
Setter’s solution : link
Tester’s solution: link