CF2190G Maximize Determinant

如果一个 $n \times n$ 的矩阵 $B$ 满足：对于每一行 $i$，都存在一段连续的列区间 $[l_i, r_i]$（$1 \le l_i \le r_i \le n$），使得该行在区间 $[l_i, r_i]$ 范围内的元素全为 $1$，其他位置全为 $0$，那么称 $B$ 为区间矩阵。形式化地，$B_{i, j} = 1$ 当且仅当 $l_i \le j \le r_i$，否则 $B_{i, j} = 0$。 现在给定一个整数 $n$ 和一个初始的区间矩阵 $A$，用 $n$ 个三元组 $(l_i, r_i, a_i)$ 描述。第 $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$ 行，每行三个整数 $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$。

对于每组测试用例，输出一个整数，表示将矩阵的行列式调整为 $X$ 所需的最小总代价。

在第一个例子中，$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$，这就是答案。 由 ChatGPT 5 翻译