← 返回题目列表

Codeforces · 2122/B

B. 堆洗牌

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

给你 $$$n$$$ 二进制堆,其中第 $$$i$$$ 个由顶部的 $$$a_i$$$ 零和底部的 $$$b_i$$$ 组成。

在一次操作中,您可以获取 顶部元素 任何一堆并将其移动到任何一堆中的任何位置,包括它被取出的那堆。

第一个示例测试用例的解决方案。
计算使第 $$$i$$$ 堆由顶部的 $$$c_i$$$ 零和底部的 $$$d_i$$$ 组成的最少操作数。

输入

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

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

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含四个整数 $$$a_i$$$、$$$b_i$$$、$$$c_i$$$、$$$d_i$$$ ($$$0 \leq a_i, b_i, c_i, d_i \leq 10^9$$$) — 原始值和目标值第 $$$i$$$ 堆的状态。

保证存在将桩转换为目标状态的一系列操作。

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

输出

对于每个测试用例,输出一个整数——达到目标状态所需的最少操作数。

示例

输入
复制

3
2
1 3 1 2
1 1 1 2
3
2 0 2 2
0 1 1 0
1 1 0 0
3
1 2 1 2
3 4 3 4
0 0 0 0

输出
复制

2
3
0

注意

第一个测试用例的解决方案如语句所示。

在第二个测试用例中,最佳解决方案是执行以下操作:

在第三个测试用例中,所有桩都已处于目标状态。