CF2190G.Maximize Determinant

An $n \times n$ matrix $B$ is called an interval matrix if for each row $i$, there exists a contiguous range of columns $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) filled with ones, while all other elements in the row are zero. Formally, $B_{i, j} = 1$ if $l_i \le j \le r_i$, and $B_{i, j} = 0$ otherwise.

You are given an integer $n$ and an initial interval matrix $A$, described by $n$ triples $(l_i, r_i, a_i)$. The $i$-th row of $A$ corresponds to the interval $[l_i, r_i]$, and $a_i$ is the cost associated with modifying this row.

Let $\mathcal{S}$ be the set of all possible $n \times n$ interval matrices. We define $X$ as the maximum possible determinant among them: $$ X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B). $$ (Note that $|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n$, as each row can be any valid interval)

Your goal is to transform $A$ into a matrix $A'$ such that $\operatorname{det}(A') = X$. To achieve this, you can perform the following operation any number of times:

• Choose a row index $i$ ($1 \le i \le n$) and a new valid interval $[L, R]$ ($1 \le L \le R \le n$).
• Replace the current interval of the $i$-th row with $[L, R]$.
• The cost of this operation is $a_i$.

Find the minimum total cost required to make the determinant of the matrix equal to $X$.

一个 $n \times n$ 矩阵 $B$ 被称为区间矩阵，如果对每一行 $i$，均存在一个连续的列区间 $[l_i, r_i]$（其中 $1 \le l_i \le r_i \le n$），使得该区间内的所有元素均为 $1$，而该行其余位置的元素均为 $0$。形式化地，$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$ 所需的最小总代价。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the size of the matrix.

The next $n$ lines describe the rows of the matrix $A$. The $i$-th of these lines contains three integers $l_i$, $r_i$, and $a_i$ ($1 \le l_i \le r_i \le n$, $1 \le a_i \le 10^9$) — the interval boundaries and the cost of modifying the $i$-th row.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single integer — the minimum total cost required to make $\operatorname{det}(A) = X$.

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

In the first example, $n = 2$ and it can be shown that $X = 1$. The matrix is $A = \begin{bmatrix} 1 & 0\\0 & 1\end{bmatrix}$. Since $\operatorname{det}(A) = 1$, no operations are needed.

In the second example, $X$ is still $1$, but the matrix is $A = \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix}$. The determinant is $-1$, so we must transform the matrix.

It can be proven that it is impossible to reach a determinant of $1$ with a single operation. Therefore, we must modify both rows. One possible sequence of operations is:

\\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}

The final matrix has a determinant of $1$. The total cost is $a_2 + a_1 = 1 + 1 = 2$, which is the answer.

在第一个例子中，$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$，即为答案。