← 返回题目列表

Codeforces · 1691/E

E. 组数

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

数轴上给出了 $$$n$$$ 彩色线段。每个部分的颜色为红色或蓝色。第 $$$i$$$ 段可以由元组 $$$(c_i, l_i, r_i)$$$ 表示。该线段包含 $$$[l_i, r_i]$$$(含)范围内的所有点,其颜色由 $$$c_i$$$ 表示:

- 如果$$$c_i = 0$$$,则它是红色段;
- 如果 $$$c_i = 1$$$,则它是蓝色段。

如果两个不同颜色的线段至少共享一个公共点,我们就说它们是相连的。如果两个线段直接连接或通过一系列直接连接的线段连接,则它们属于同一组。求线段组的数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 段数。

接下来的 $$$n$$$ 行包含三个整数 $$$c_i, l_i, r_i$$$ ($$$0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$$$),描述第 $$$i$$$ 段。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 $$$k$$$,即段组的数量。

示例

输入 #1

2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4

输出 #1

2
3

注意

在第一个示例中,有 $$$5$$$ 段。线段 $$$1$$$ 和 $$$2$$$ 是相连的,因为它们具有不同的颜色并且共享一个点。此外,线段 $$$2$$$ 和 $$$3$$$ 是相连的,线段 $$$4$$$ 和 $$$5$$$ 也是相连的。因此,有两组:一组包含段 $$$\{1, 2, 3\}$$$,另一组包含段 $$$\{4, 5\}$$$。