P8500 [NOI2022] Bubble Sort

Recently, Little Z has become very interested in bubble sort. Below is the pseudocode of bubble sort: ``` Input: a sequence a[1...n] of length n Output: the result of sorting a in nondecreasing order for i = 1 to n do: for j = 1 to n - 1 do if (a[j] > a[j + 1]) swap the values of a[j] and a[j + 1] ``` The number of swaps in bubble sort is defined as **the number of swaps performed during sorting**, that is, the number of times **line 6** of the bubble sort pseudocode above is executed. He wants to find a sequence with as few swaps as possible. # Background

All sequences studied by Little Z consist of nonnegative integers. The length of the sequence is $n$, and it must satisfy $m$ additional constraints. The $i$-th constraint is: Among the numbers whose indices lie in $[L_i, R_i]$, i.e., $a_{L_i}, a_{L_{i+1}},\dots,a_{R_i}$, the minimum value is **exactly $\boldsymbol{V_i}$**. He knows that bubble sort often times out. Therefore, he wants to know: among all sequences that satisfy the additional constraints, what is the minimum possible number of swaps performed by bubble sort?

This problem contains multiple test cases. The first line of input contains a positive integer $T$. For each test case, the first line contains two positive integers $n, m$. The data guarantee that $1 \leq n, m \leq 10^6$. In the next $m$ lines, each line contains three nonnegative integers $L_i, R_i, V_i$, representing one additional constraint. The data guarantee that $1 \leq L_i \leq R_i \leq n$, and $0 \leq V_i \leq 10^9$.

Output $T$ lines in total, each line containing one integer. For each test case, if there exists a sequence satisfying all $m$ additional constraints, output the minimum number of bubble sort swaps among all such sequences. If no sequence satisfies all constraints, output $-1$.

**[Sample Explanation #1]** The constraints for this test case are $a_1 = 2022$ and $\min\{a_2, a_3\} = 39$. If $a_2 = 39$ and $39 \leq a_3 < 2022$, then bubble sort performs swaps only in the first pass. In this pass, it swaps $a_1, a_2$ and $a_2, a_3$, so the total number of swaps is $2$. If $a_2 = 39$ and $a_3 \geq 2022$, then bubble sort performs swaps only in the first pass. In this pass, it swaps only $a_1, a_2$, so the total number of swaps is $1$. If $a_3 = 39$ and $39 < a_2 < 2022$, then in the first pass bubble sort swaps $a_1, a_2$ and $a_2, a_3$, and in the second pass it swaps $a_1, a_2$. The total number of swaps is $3$. If $a_3 = 39$ and $a_2 \geq 2022$, then in the first pass bubble sort swaps $a_2, a_3$, and in the second pass it swaps $a_1, a_2$. The total number of swaps is $2$. Therefore, the minimum number of swaps is $1$. ---- **[Sample #2]** See `bubble/bubble2.in` and `bubble/bubble2.ans` in the attachment. ---- **[Sample #3]** See `bubble/bubble3.in` and `bubble/bubble3.ans` in the attachment. This sample satisfies the conditions of test points $8 \sim 10$. ---- **[Sample #4]** See `bubble/bubble4.in` and `bubble/bubble4.ans` in the attachment. This sample satisfies the conditions of test points $13 \sim 14$. ---- **[Sample #5]** See `bubble/bubble5.in` and `bubble/bubble5.ans` in the attachment. This sample satisfies the conditions of test points $15 \sim 16$. ---- **[Sample #6]** See `bubble/bubble6.in` and `bubble/bubble6.ans` in the attachment. This sample satisfies the conditions of test points $23 \sim 25$. ---- **[Constraints]** This problem has $25$ test points. All test points satisfy: $1 \leq T \leq 1000$, $1 \leq \sum n, \sum m \leq 10^6$, $1 \leq L_i \leq R_i \leq n$, $0 \leq V_i \leq 10^9$. Here, $\sum n$ and $\sum m$ denote the total sum of $n$ and the total sum of $m$ over all test points. The meanings of $\sum n^2, \sum m^2, \sum n^3, \sum m^3$ are similar. | Test Points | Constraints | Special Property | |:-----------------:|:----------------------------------------------------------:|:----------------:| | $1 \sim 4$ | $n,m \leq 7$, and at most $2$ test cases do not satisfy $n, m \leq 5$ | | | $5 \sim 7$ | $n,m \leq 17$, and at most $3$ test cases do not satisfy $n, m \leq 9$ | A | | $8 \sim 10$ | $n,m \leq 100$, $\sum n^3,\sum m^3 \leq 4 \times 10^7$ | A | | $11 \sim 12$ | $n,m \leq 2000$, $\sum n^2,\sum m^2 \leq 4 \times 10^7$ | A | | $13 \sim 14$ | $n,m \leq 2000$, $\sum n^2,\sum m^2 \leq 4 \times 10^7$ | B | | $15 \sim 16$ | $n,m \leq 2000$, $\sum n^2,\sum m^2 \leq 4 \times 10^7$ | C | | $17 \sim 18$ | $n,m \leq 2000$, $\sum n^2,\sum m^2 \leq 4 \times 10^7$ | | | $19$ | $\sum n,\sum m \leq 10^6$ | A | | $20$ | $\sum n,\sum m \leq 10^6$ | B | | $21 \sim 22$ | $\sum n,\sum m \leq 10^6$ | C | | $23 \sim 25$ | $\sum n,\sum m \leq 10^6$ | | Special property A: For $1 \leq i \leq m$, $0 \leq V_i \leq 1$. Special property B: For $1 \leq i \leq m$, $L_i = R_i$. Special property C: The $m$ intervals $[L_i, R_i]$ given in the input are pairwise disjoint. ---- **[Hint]** For some test points, the input size is large. We recommend using a faster input method. Translated by ChatGPT 5