A Story of One Country (Hard)
Contest: Codeforces Round 567 (Div. 2)
Difficulty rating: 3000
Tags: brute force, greedy, sortings

This problem differs from the previous problem only in constraints.

Petya decided to visit Byteland during the summer holidays. It turned out that the history of this country is quite unusual.

Initially, there were $$$n$$$ different countries on the land that is now Berland. Each country had its own territory that was represented as a rectangle on the map. The sides of the rectangle were parallel to the axes, and the corners were located at points with integer coordinates. Territories of no two countries intersected, but it was possible that some territories touched each other. As time passed, sometimes two countries merged into one. It only happened if the union of their territories was also a rectangle. In the end only one country remained — Byteland.

Initially, each country had a rectangular castle inside its territory. Its sides were parallel to the axes and its corners had integer coordinates. Some castles might touch the border of the corresponding country and sides or other castles. Miraculously, after all the unions the castles are still intact. Unfortunately, their locations are the only information we have to restore the initial territories of the countries.

The possible formation of Byteland. The castles are shown in blue.

Petya wonders why no information about the initial countries remained. He suspected that the whole story is a fake. You were recommended to him as a smart person. Please check whether or not there exists a possible set of initial territories that could make the story true.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — the number of countries and castles.

Each of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th castle, where $$$(a_i, b_i)$$$ are the coordinates of the lower left corner and $$$(c_i, d_i)$$$ are the coordinates of the upper right corner.

It is guaranteed that no two castles intersect, however, they may touch.

Output format:
If there exists a possible set of territories that satisfies the story, print "YES", otherwise print "NO".

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
The castles in the first and second examples are shown on the pictures below.

Example input:
4
0 0 1 2
0 2 1 3
1 0 2 1
1 1 2 3

Example output:
YES

Example input:
4
0 0 2 1
1 2 3 3
2 0 3 2
0 1 1 3

Example output:
NO

Editorial:
We can rephrase the problem as follows:
There is a set of non-intersecting rectangles on the plane. Let's say, that some rectangular area on the plane is good, if it contains exactly one rectangle in it or there exists a vertical or horizontal cut, which cuts the area into two good areas. You are asked to check whether the area $$$[0; 10^9] \times [0; 10^9]$$$ is good.
It's easy to see that it is exactly the same process as in the statement, except we don't merge countries into one, we look at the reversed process, where we split one country into many.
Also let's notice, that when we found some cutting line, which doesn't goes through inner part of any rectangle, we can always apply it to separate our area into two. We can do that, since our predicate of set of rectangles being nice is monotonic: if we replace set of rectangles with its subset, it only can make better.
Now let's analyze when the cut is good:
This already gives us a solution in $$$\mathcal{O}(n^2 \log)$$$, which passes the easy version of the problem. Simply solve the problem recursively, sorting rectangles as shown above. (and symmetrically for horizontal cuts) and try finding a cut. Once we find it, solve the problem recursively.
Now we have working time: $$$T(n) = T(x) + T(n - x) + \mathcal{O}(n \log n)$$$, where $$$x$$$ is a size of one part of the cut. The worse case is $$$x = 1$$$, so $$$T(n) = \mathcal{O}(n^2 \log)$$$. $$$\square$$$
For the full version we need a faster solution.
The key idea is: let's cut always "smaller from larger". Suppose we are magically able to find any valid cut in $$$\mathcal{O}(1)$$$ (basically the number $$$x$$$). Then we could have spent $$$\mathcal{O}(x)$$$ to cut out the smaller part into new recursive call. While we can continue the process of cutting with the remaining rectangles in this recursion call.
This solution works in $$$\mathcal{O}(n \log n)$$$: Each time the size of problem reduces at least twice when we go into recursion, so there are only $$$\log$$$ levels.
However we need to handle "magic" here. For example one could have used a segment tree to implement all mentioned above (it would give a $$$\mathcal{O}(n \log^2)$$$ time). But there is a simpler solution!
Let's sort rectangles using all $$$4$$$ possible sortings. And let's iterate over all this sortings simultaneously. We need $$$4$$$ directions instead of $$$2$$$, because if we would e.g. only iterate from let to right, we wouldn't be able to cut out the "smaller" from "larger", in case the "smaller" is to the right of "larger". So we want to both go from left to right and from right to left.
When in one of the directions we see a valid place to make a cut, we remove all the rectangles into the separate recursion call. We also mark all those rectangles in the current recursion call as deleted and start the procedure of cutting again. We can simply skip the rectangles marked as deleted when we encounter them. For example we could use a linked list for that:
So now we got a solution in $$$\mathcal{O}(n \log^2)$$$: one logarithm is from cutting smaller from larger and one logarithm is from sorting.
One could drop the second logarithm. For that we should sort all rectangles at the beginning and then carefully pass the correct ordering down the recursion. But that wasn't required.