CF1389D Segment Intersections

给定两组线段 $[al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]$ 和 $[bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]$。 初始时，所有 $[al_i, ar_i]$ 都等于 $[l_1, r_1]$，所有 $[bl_i, br_i]$ 都等于 $[l_2, r_2]$。 每一步，你可以选择任意一条线段（可以是第一组或第二组中的任意一条），并将其延长 $1$。也就是说，假设你选择了线段 $[x, y]$，你可以将其变为 $[x-1, y]$ 或 $[x, y+1]$。 我们定义总交集 $I$ 为每对对应线段交集长度之和，即 $I = \sum\limits_{i=1}^{n} \text{intersection\_length}([al_i, ar_i], [bl_i, br_i])$。空交集的长度为 $0$，线段 $[x, y]$ 的长度为 $y - x$。 请问，最少需要多少步才能使 $I \geq k$？

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例数。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq 10^9$），分别表示线段组的长度和所需的最小总交集。 第二行包含两个整数 $l_1$ 和 $r_1$（$1 \leq l_1 \leq r_1 \leq 10^9$），表示所有 $[al_i, ar_i]$ 的初始区间。 第三行包含两个整数 $l_2$ 和 $r_2$（$1 \leq l_2 \leq r_2 \leq 10^9$），表示所有 $[bl_i, br_i]$ 的初始区间。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $t$ 行，每行一个整数，表示对于每个测试用例，使 $I \geq k$ 所需的最小步数。

在第一个测试用例中，可以通过如下策略实现总交集 $5$： - 将 $[al_1, ar_1]$ 从 $[1, 2]$ 变为 $[1, 4]$，共 $2$ 步； - 将 $[al_2, ar_2]$ 从 $[1, 2]$ 变为 $[1, 3]$，共 $1$ 步； - 将 $[bl_1, br_1]$ 从 $[3, 4]$ 变为 $[1, 4]$，共 $2$ 步； - 将 $[bl_2, br_2]$ 从 $[3, 4]$ 变为 $[1, 4]$，共 $2$ 步。 最终，$I = \text{intersection\_length}([al_1, ar_1], [bl_1, br_1]) + \text{intersection\_length}([al_2, ar_2], [bl_2, br_2]) + \text{intersection\_length}([al_3, ar_3], [bl_3, br_3]) = 3 + 2 + 0 = 5$。 在第二个测试用例中，可以将 $[al_1, ar_1]$ 变为 $[0, 1000000000]$，需要 $1000000000$ 步；将 $[bl_1, br_1]$ 变为 $[0, 1000000000]$，也需要 $1000000000$ 步。 在第三个测试用例中，总交集 $I$ 已经等于 $10 > 3$，因此不需要任何操作。 由 ChatGPT 4.1 翻译