P16582 [GKS 2016 #B] Watson and Intervals

Sherlock 和 Watson 在编程课程中已经掌握了 C++ 语言的复杂性，因此他们开始研究算法问题。在今天的课堂上，老师介绍了合并一维区间的问题。给出了 $N$ 个区间，第 $i$ 个区间由闭端点 $[L_i, R_i]$ 定义，其中 $L_i \le R_i$。 老师将一组区间的**覆盖面积**定义为至少出现在一个区间中的整数的个数。（形式化地说，若存在某个 $j$ 使得 $L_j \le p \le R_j$，则整数 $p$ 对覆盖面积有贡献。） 现在，Watson 总是喜欢挑战 Sherlock。他要求 Sherlock 恰好移除一个区间，使得剩余区间的覆盖面积最小。请帮助 Sherlock 找出在恰好移除 $N$ 个区间中的一个之后，剩余区间的最小可能覆盖面积。

每个测试用例由一行八个整数组成：$N$、$L_1$、$R_1$、$A$、$B$、$C_1$、$C_2$ 和 $M$。其中 $N$ 是区间的数量，其余七个值是参数，你需要使用它们来生成其他区间，方法如下： 首先定义 $x_1 = L_1$ 和 $y_1 = R_1$。然后，使用下面的递推式生成 $i = 2$ 到 $N$ 的 $x_i$、$y_i$： * $x_i = (A \times x_{i-1} + B \times y_{i-1} + C_1) \bmod M$。 * $y_i = (A \times y_{i-1} + B \times x_{i-1} + C_2) \bmod M$。 对于所有 $i = 2$ 到 $N$，我们定义 $L_i = \min(x_i, y_i)$，$R_i = \max(x_i, y_i)$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在恰好移除一个区间之后，剩余所有区间的最小可能覆盖面积。

在样例 $1$ 中，使用生成方法得到的区间集合为：$\{[1, 1]\}$。移除唯一的区间后，覆盖面积为 $0$。 在样例 $2$ 中，使用生成方法得到的区间集合为：$\{[2, 5], [3, 5], [4, 7]\}$。移除第一个、第二个或第三个区间后，剩余区间的覆盖面积分别为 $5$、$6$ 和 $4$。 在样例 $3$ 中，使用生成方法得到的区间集合为：$\{[3, 4], [1, 9], [0, 8], [2, 4]\}$。移除第一个、第二个、第三个或第四个区间后，剩余区间的覆盖面积分别为 $10$、$9$、$9$ 和 $10$。 ### 限制条件 $1 \le T \le 50$。 $0 \le L_1 \le R_1 \le 10^9$。 $0 \le A \le 10^9$。 $0 \le B \le 10^9$。 $0 \le C_1 \le 10^9$。 $0 \le C_2 \le 10^9$。 $1 \le M \le 10^9$。 **小数据集（测试集 1 – 可见）** $1 \le N \le 1000$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 5 \times 10^5\ (500000)$。 翻译由 DeepSeek V4 Pro 完成