P11103 [ROI 2022] Challenge (Day 2)

Translated from [ROI 2022 D2T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf). In the design class at the Sirius Educational Center, a team designed an industrial robot. These robots will put parts into $n$ containers numbered from $1$ to $n$. Each container can hold at most $a_i$ parts. There are $m$ robots in total. Initially, robot $j$ has $c_j$ parts. Also, robot $j$ has a working range determined by two numbers $l_j$ and $r_j$, meaning it can only put parts into containers with indices from $l_j$ to $r_j$ (inclusive). Robots try to put as many parts as possible into the containers. Robots are of two types. If a robot has type $t_j = 0$, then its working range always stays unchanged. If a robot has type $t_j = 1$, it can change its working range. If the container numbered $x$ is designated as the most important container, then the working range of every type $1$ robot will expand so that this range contains container $x$. In other words, for a type $1$ robot $j$, its working range will become $[\min(l_j,x),\max(r_j,x)]$.

For each $x$ from $1$ to $n$, compute the maximum number of parts that the robots can put into the containers when container $x$ is considered the most important container.

This problem has multiple test cases. The first line contains an integer $t$, the number of test cases. For each test case, the first line contains two integers $n$ and $m$, the number of containers and the number of robots. The next line contains $n$ integers $a_1,a_2,\dots,a_n$, the capacities of the containers. Each of the next $m$ lines contains four integers $l_j, r_j, c_j, t_j$, describing the robot's working range, the number of parts it initially carries, and the robot type.

For each test case, output $n$ integers, representing the answers for all $x$ from $1$ to $n$.

For $100\%$ of the testdata, $1 \le t \le 200000$, $1 \le n,m \le 200000$, $0 \le a_i \le 10^9$, $1 \le l_j \le r_j \le n$, $0 \le c_j \le 10^9$, $t_j \in \{0, 1\}$. | Subtask | Score | $\sum n\le$ | $\sum m\le$ | Other special properties | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $100$ | $100$ | $m=1$ | | $2$ | $7$ | $100$ | $100$ | | | $3$ | $6$ | $2000$ | $2000$ | | | $4$ | $6$ | $20000$ | $200$ | | | $5$ | $12$ | $10^5$ | $2000$ | | | $6$ | $17$ | $20000$ | $20000$ | $t_i=1$ | | $7$ | $8$ | $10^5$ | $10^5$ | $l_i\le l_{i+1},r_i\le r_{i+1},t_i=1$ | | $8$ | $8$ | $10^5$ | $10^5$ | $t_i=1$ | | $9$ | $13$ | $10^5$ | $10^5$ | For all robots with $t_i=0$, $r_i\le50$ or $l_i>n-50$ | | $10$ | $4$ | $10^5$ | $10^5$ | $a_i=1$ | | $11$ | $6$ | $10^5$ | $10^5$ | | | $12$ | $3$ | $2\times10^5$ | $2\times10^5$ | | Translated by ChatGPT 5