题目描述

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$ 是在恰好移除一个区间之后，剩余所有区间的最小可能覆盖面积。

3
1 1 1 1 1 1 1 1
3 2 5 1 2 3 4 10
4 3 4 3 3 8 10 10

Case #1: 0
Case #2: 4
Case #3: 9

提示

在样例 $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 完成