P12691 [KOI 2022 Round 1] 补给

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在一个二维平面上有 $N$ 个军事基地。第 $i$ 个基地的位置是坐标 $(X_i, Y_i)$。 负责该区域的补给部队打算对所有基地进行补给。每个第 $i$ 个基地可以接受补给的日期是从第 $A_i$ 天到第 $B_i$ 天之间的某一天。 由于正处于战争时期，补给部队必须保持整体从左上方向右下方推进的队形，因此只能朝右上方向前进。因此，必须为每个基地分配一个具体的补给日期 $V_i$，使得满足以下所有条件： - 对所有的 $i$，都满足 $A_i \leq V_i \leq B_i$； - 对所有 $i, j$ 满足 $X_i < X_j$ 且 $Y_i < Y_j$ 时，必须满足 $V_i < V_j$； - 对所有 $i \ne j$，必须有 $V_i \ne V_j$。 给定各个基地的位置 $(X_i, Y_i)$ 以及它们可接受补给的日期范围 $[A_i, B_i]$，请编写一个程序判断是否存在一种补给日期的分配方案，满足上述所有条件。如果存在，输出 YES，并按基地编号顺序输出每个基地的分配日期；如果不存在，输出 NO。 下图展示了一个包含 6 个基地的示例情况。图中的每个点代表一个基地，点的右上方标注了该基地可以接受补给的日期范围。  下图还展示了为这些基地安排补给日期的一个可行方案，点的右下方标注了分配给每个基地的具体补给日期。图中弯曲的线表示补给部队在第 2 天至第 3 天之间可能处于的位置范围。 

第一行输入一个整数 $N$，表示基地的数量。 接下来 $N$ 行，每行输入四个整数 $X_i$, $Y_i$, $A_i$, $B_i$，以空格分隔，表示第 $i$ 个基地的位置和其可接受补给的日期范围。

如果存在合法的补给方案，第一行输出 `YES`，第二行输出 $N$ 个整数，表示按基地编号顺序分配的补给日期，数与数之间以空格分隔。 如果不存在合法的补给方案，输出 `NO`。

**约束条件** - 所有给定的数都是整数。 - $1 \leq N \leq 250\,000$ - $1 \leq A_i \leq B_i \leq N$ - $1 \leq X_i \leq N$ - $1 \leq Y_i \leq N$ - 所有 $X_i$ 互不相同，即 $i \ne j$ 时 $X_i \ne X_j$ - 所有 $Y_i$ 互不相同，即 $i \ne j$ 时 $Y_i \ne Y_j$ **子任务** 1. （13 分）$N \leq 10$ 2. （18 分）$N \leq 2\,500$ 3. （22 分）对所有 $i$，满足 $B_i = N$ 4. （47 分）无附加限制