SP14742 BRDGHRD - Building Bridges(HARD)

部落很快意识到，仅仅依靠通信是不够的，他们需要亲自会面联手抵抗终结者。然而，一条深谷横亘在前，他们必须跨越。两边的陡峭悬崖上已经标记出了一些点，这些点可以作为桥梁的起点和终点。然而，还未开工，一位女巫Chudael预言了一个条件：桥梁只能连接相对应的端点，即从一侧第 $i$ 个端点开始的桥只能连接到另一侧的第 $i$ 个端点。若不遵守这一法则，将导致部落的毁灭。部落希望在这一限制下，修建尽可能多的不重叠桥梁。 ### 输入格式 输入的第一行为测试用例的数量 $t$。接下来的 $3 \times t$ 行，每三个作为一组，为一个测试用例。每个测试用例的第一行是端点的数量 $n$（$1 \le n \le 10^5$）。第二行是第一侧的端点 $x$ 坐标列表，第三行为另一侧相应端点的 $x$ 坐标列表。端点是按照被识别的顺序提供的。$x$ 坐标的范围是 $-10^6$ 到 $10^6$。 ### 输出格式 对于每个测试用例，输出一行，表示在上述限制下可以修建的最大桥梁数量。 ### 示例 ``` 输入： 3 4 2 5 8 10 6 4 1 2 3 5 3 10 6 4 1 6 1 2 3 4 5 6 3 4 5 6 1 2 输出： 2 2 4 解释：在第一个测试用例中，可以在两侧的第 3 和第 4 个端点之间建造两座不重叠的桥梁。 （本题参考来源：http://www.spoj.com/problems/BRIDGE.） ``` ### 数据范围与提示 - $1 \le t \le 10^5$ - $1 \le n \le 10^5$ - $-10^6 \le x_i \le 10^6$ **本翻译由 AI 自动生成**

无

无