P4793 [AHOI2008] Rectangular Treasure Land

The most famous game on Happy Island is a treasure-hunting game. Xiaokeke arrives at the treasure burial area, which is an open field. The treasures are buried scattered underground in this field, and the task now is to dig them out one by one. To indicate possible treasure locations, the organizers treat this open field as the first quadrant (including the origin and the positive coordinate axes). They divide all possible treasure locations into rectangular plots, and provide the coordinates of these rectangular plots to the contestants. The hint for digging is very simple: if a certain rectangular plot is contained in at least one other rectangular plot, then there must be a treasure buried inside that rectangular plot. In fact, these treasures are exquisite souvenirs. Whoever digs up a souvenir gets to keep it. Xiaokeke wants to end this journey perfectly, and with your help he is full of confidence. You only need to tell him: how many rectangular plots are guaranteed to contain a treasure. Victory is just ahead. Keep it up.

The first line contains an integer $N\leq 200000$, indicating the number of rectangles. The next $N$ lines each contain $4$ integers $x_1,\,y_1,\,x_2,\,y_2$, describing a rectangle. Here, $(x_1,\,y_1)$ is the coordinate of the lower-left corner, and $(x_2,\,y_2)$ is the coordinate of the upper-right corner. Each $x$ value or $y$ value appears at most once.

Contains only one integer, the number of rectangular plots that are guaranteed to contain a treasure.

In $30\%$ of the testdata, $N\leq 5000$. In $70\%$ of the testdata, $N\leq 50000$. In $100\%$ of the testdata, $N\leq 200000$. In all testdata, each $x$ value or $y$ value appears at most once. The coordinate range is $2\times 10 ^ 6$. Translated by ChatGPT 5