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](https://en.wikipedia.org/wiki/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 $ .

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 $ .

For each test case, print a single integer — the minimum total cost required to make $ \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.