CF1181E2 A Story of One Country (Hard)

本题与上一题的区别仅在于数据范围。 Petya 决定在暑假期间访问 Byteland。结果发现，这个国家的历史非常独特。 最初，在现在的 Berland 这片土地上有 $n$ 个不同的国家。每个国家都有自己的领土，在地图上表示为一个矩形。矩形的边平行于坐标轴，顶点的坐标均为整数。任意两个国家的领土没有重叠，但可能会相互接触。随着时间的推移，有时两个国家会合并成一个国家。只有当它们领土的并集也是一个矩形时，才能合并。最终，只剩下一个国家——Byteland。 最初，每个国家的领土内都有一座矩形城堡。城堡的边平行于坐标轴，顶点的坐标均为整数。有些城堡可能会接触到所属国家的边界、边或其他城堡。奇迹般地，经过所有合并后，这些城堡依然完好无损。不幸的是，我们现在仅能通过这些城堡的位置来还原最初各国的领土。  Byteland 的可能形成过程。蓝色部分为城堡。Petya 很疑惑为什么没有留下关于最初各国的任何信息。他怀疑整个故事都是假的。有人向他推荐了你，认为你很聪明。请你判断是否存在一种可能的初始领土划分，使得这个故事成立。

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$），表示国家和城堡的数量。 接下来的 $n$ 行，每行包含四个整数 $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$），表示第 $i$ 个城堡的坐标，其中 $(a_i, b_i)$ 是左下角坐标，$(c_i, d_i)$ 是右上角坐标。 保证任意两个城堡没有重叠，但可能会接触。

如果存在一种可能的初始领土划分满足题意，输出 "YES"；否则输出 "NO"。 可以用任意大小写输出每个字母。

下图展示了第一个和第二个样例中的城堡。   由 ChatGPT 4.1 翻译