CF1181E2.A Story of One Country (Hard)

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.

本题与上一题的区别仅在于约束条件。

佩蒂亚决定在暑假期间访问比特兰（Byteland）。结果发现，这个国家的历史非常特别。

最初，在如今被称为贝尔兰（Berland）的这片土地上，存在 $n$ 个互不相同的国家。每个国家都拥有自己的领土，该领土在地图上表示为一个矩形。矩形的边与坐标轴平行，且其顶点均位于整数坐标点上。任意两个国家的领土互不相交，但允许彼此相邻（即边界接触）。随着时间推移，有时两个国家会合并为一个国家——仅当它们领土的并集仍构成一个矩形时，合并才可能发生。最终，只剩下一个国家——比特兰（Byteland）。

最初，每个国家都在其领土内部建有一座矩形城堡。城堡的边也与坐标轴平行，且其顶点同样位于整数坐标点上。某些城堡可能与对应国家的边界或与其他城堡的边相接触。奇迹般地，在所有合并过程结束后，这些城堡依然完整无损。不幸的是，如今我们仅掌握这些城堡的位置信息，而必须据此还原出最初的各国领土。

比特兰可能的形成过程示意图。图中蓝色区域表示各城堡。

佩蒂亚疑惑：为何关于最初各国的任何信息都已消失？他怀疑整段历史纯属虚构。你因聪明过人而被推荐给他。请判断：是否存在一组满足条件的初始领土划分，使得上述故事成立？

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 \lt c_i \leq 10^9$, $0 \leq b_i \lt 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.

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 国家与城堡的数量。

接下来的 $n$ 行，每行包含四个整数 $a_i, b_i, c_i, d_i$（$0 \leq a_i \lt c_i \leq 10^9$，$0 \leq b_i \lt d_i \leq 10^9$）—— 第 $i$ 个城堡的坐标，其中 $(a_i, b_i)$ 是左下角坐标，$(c_i, d_i)$ 是右上角坐标。

保证任意两个城堡互不相交，但它们可以相邻（即边界可以重合）。

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).

如果存在一组满足故事情节的领土，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写（大写或小写）输出每个字母。

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

第一个和第二个样例中的城堡如下面的图片所示。