← 返回题目列表

Codeforces · 2034/G2

G2. Simurgh 的手表(硬版)

中文机器翻译题面 查看原题

问题的两个版本之间的唯一区别在于是在所有点还是仅在整数点考虑重叠。

传说中的 Simurgh,一种神话鸟,负责看守广阔的土地,为此,她招募了 $$$n$$$ 警惕的战士。每个战士在特定时间段 $$$[l_i, r_i]$$$ 内保持警惕,其中 $$$l_i$$$ 为开始时间(含),$$$r_i$$$ 为结束时间(含),均为正整数。

Simurgh 值得信赖的顾问之一 Zal 担心,如果多个战士同时驻扎并且都穿着相同的颜色,他们之间的区别可能会丢失,从而导致手表混乱。为了防止这种情况发生,每当多个武士在同一整数时刻进行警戒时,必须至少有一种颜色恰好由一名武士穿着。

因此,任务是确定所需的最小颜色数,并为每个战士的段 $$$[l_i, r_i]$$$ 分配一种颜色 $$$c_i$$$,这样,对于至少一个段中包含的每个(整数)时间 $$$t$$$,存在一种颜色恰好属于包含 $$$t$$$ 的一个段。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

对于每个测试用例:

- 第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — Simurgh 驻扎的战士数量。
- 接下来的 $$$n$$$ 行每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$) — 战士手表段的开始和结束时间。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例:

- 输出所需的最小颜色数$$$k$$$。
- 然后,输出一行 $$$n$$$ 整数 $$$c_i$$$ ($$$1 \leq c_i \leq k$$$),其中每个 $$$c_i$$$ 是分配给第 $$$i$$$ 个战士的颜色。

示例

输入 #1

3
5
1 4
2 8
3 7
5 10
6 9
5
1 5
2 6
3 7
4 7
6 7
5
4 9
8 17
2 15
12 19
6 13

输出 #1

2
1 2 2 1 2
2
1 2 2 2 1
3
1 1 2 3 1

注意

我们可以将每个战士的手表段表示为X轴上的一个区间;

在测试用例 1 中,可以对间隔进行着色,如下所示(间隔使用所选颜色进行着色;如果该颜色在该时间点恰好出现一次,则对区域进行着色):

在测试用例 2 中,间隔可以着色,如下所示:

在测试用例 3 中,间隔可以着色,如下所示: