P16319 [ICPC 2023 Jinan R] Railway Tour

$\textbf{Please note that this problem has an unusual memory limit.}$ "Railway Tour" is a German-style board game themed around railways. In the game, players play train cards and build railways on the map. The score is determined by the total length of railways built and whether the player can connect faraway cities. The cities that need to be connected are determined by the drawn ticket cards. :::align{center}  A photo taken by BoardGameGeek user @garyjames ::: Consider a one-dimensional version of the game. There are $(n + 1)$ cities in a line, numbered from $0$ to $n$ from left to right. For each $1 \le i \le n$, you may place a railway between city $(i - 1)$ and city $i$ to connect them. There are $m$ ticket cards that reward the player for connecting cities. The $i$-th card can be described by three integers $l_i$, $r_i$, and $v_i$, meaning that if city $l_i$ and city $r_i$ can be connected by railways (that is, for all $l_i < j \le r_i$, there is a railway between city $(j - 1)$ and city $j$), you will gain $v_i$ points. For each $1 \le k \le n$, compute the maximum score when you place exactly $k$ railways. If you do not get any reward, your score is $0$.

There are multiple test cases. The first line contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^4$), representing the maximum number of railways you may place and the number of ticket cards for rewards. In the next $m$ lines, the $i$-th line contains three integers $l_i$, $r_i$, and $v_i$ ($0 \le l_i < r_i \le n$, $1 \le v_i \le 10^9$), meaning that if city $l_i$ and city $r_i$ can be connected by railways, you will gain $v_i$ points. It is guaranteed that the sum of all $n$ and the sum of all $m$ over all test cases are both at most $10^4$.

For each test case, output one line with $n$ integers separated by single spaces, where the $i$-th integer represents the maximum score when you place exactly $i$ railways. Please do not output extra spaces at the end of the line, otherwise your answer may be judged as wrong.

Let $(i - 1, i)$ denote a railway between city $(i - 1)$ and city $i$. For the first sample test case: - If you place $1$ railway, you can place $(3, 4)$ and then get the second reward. The answer is $2$. - If you place $2$ railways, you can place $(0, 1)$ and $(1, 2)$ and then get the first reward. The answer is $3$. - If you place $3$ railways, you can place $(0, 1)$, $(1, 2)$, and $(3, 4)$ and then get the first and second rewards. The answer is $3 + 2 = 5$. - If you place all $4$ railways, you can get all rewards. The answer is $3 + 2 + 1 = 6$. Translated by ChatGPT 5