← 返回题目列表

Codeforces · 2190/G

G. 最大化行列式

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

一个 $$$n \times n$$$ 矩阵 $$$B$$$ 称为 区间矩阵 如果对于每行 $$$i$$$,存在连续范围的列 $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$) 填充 1,而该行中的所有其他元素均为零。形式上,如果 $$$l_i \le j \le r_i$$$,则 $$$B_{i, j} = 1$$$,否则 $$$B_{i, j} = 0$$$。

给定一个整数 $$$n$$$ 和一个初始区间矩阵 $$$A$$$,由 $$$n$$$ 三元组 $$$(l_i, r_i, a_i)$$$ 描述。 $$$A$$$ 的第 $$$i$$$ 行对应于区间 $$$[l_i, r_i]$$$,$$$a_i$$$ 是与修改该行相关的成本。

令 $$$\mathcal{S}$$$ 为所有可能的 $$$n \times n$$$ 区间矩阵的集合。我们将 $$$X$$$ 定义为其中最大可能的行列式: $$X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B).$$ (注意 $$$|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n$$$,因为每行可以是任何有效区间)

您的目标是将 $$$A$$$ 转换为矩阵 $$$A'$$$,使得 $$$\operatorname{det}(A') = X$$$。为此,您可以多次执行以下操作:

  • 选择行索引 $$$i$$$ ($$$1 \le i \le n$$$) 和新的有效区间 $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$)。
  • 将第 $$$i$$$ 行的当前间隔替换为 $$$[L, R]$$$。
  • 此操作的成本为 $$$a_i$$$。

求使矩阵的行列式等于 $$$X$$$ 所需的最小总成本。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 矩阵的大小。

接下来的 $$$n$$$ 行描述了矩阵 $$$A$$$ 的行。这些行的第 $$$i$$$ 包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$a_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le a_i \le 10^9$$$) - 区间边界和修改第 $$$i$$$ 行的成本。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,打印一个整数 - 使 $$$\operatorname{det}(A) = X$$$ 所需的最小总成本。

示例

输入
复制

6
2
1 1 1
2 2 1
2
2 2 1
1 1 1
4
1 4 4
2 2 3
4 4 6
2 4 5
6
1 6 1
5 5 1000
2 4 1000
6 6 1000
3 3 1000
4 4 1000
5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
5
1 4 15
4 4 14
2 3 16
2 2 14
3 5 15

输出
复制

0
2
3
1000
4000000000
14

注意

在第一个示例中,$$$n = 2$$$,可以证明$$$X = 1$$$。矩阵为 $$$A = \begin{bmatrix} 1 & 0\\0 & 1\end{bmatrix}$$$。由于 $$$\operatorname{det}(A) = 1$$$,因此不需要任何操作。

在第二个示例中,$$$X$$$ 仍然是 $$$1$$$,但矩阵是 $$$A = \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix}$$$。行列式是$$$-1$$$,所以我们必须变换矩阵。

可以证明,通过一次操作不可能达到$$$1$$$的行列式。因此,我们必须修改这两行。一种可能的操作顺序是:

$$\begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix} \xrightarrow{i = 2, \, L = 2, \, R = 2} \begin{bmatrix} 0 & 1\\0 & 1\end{bmatrix} \xrightarrow{i = 1, \, L = 1, \, R = 2} \begin{bmatrix} 1 & 1\\0 & 1\end{bmatrix}$$

最终矩阵的行列式为 $$$1$$$。总成本为 $$$a_2 + a_1 = 1 + 1 = 2$$$,这就是答案。