P10120 "STA - R4" Iced Black Tea

 A programming site BTC has long placed "tech template problems" as the last problem of its Beginner Contest. So APJifengc got angry and poured several bottles of iced black tea onto its judging machines, causing some judging units to run $10^{12}$ times faster, making brute force as fast as the intended solution. Since BTC can no longer publish "tech template problems", the site admin of BTC wants you to maintain the number of available judging units after each time APJifengc pours iced black tea, so that they can coordinate judging resources and do post-disaster reconstruction. **Hack testdata has been added in Subtask 5 and is not scored.**

There are $n$ bots in a line. Every day, all bots drink iced black tea. You need to dynamically maintain the line of bots. There are three types of operations or queries: - `1 l r k`: bots in $[l,r]$ will drink $k$ bottles of original-flavor iced black tea, and bots outside $[l,r]$ will drink $k$ bottles of tropical-flavor iced black tea. - `2 l r k`: the BTC admin angrily destroys the bots in $[l,r]$ that, most recently, have continuously drunk at least $k$ bottles of iced black tea of the same flavor. - `3`: query how many bots are still alive. Note: In operation 2, destroying bots does not change the numbering of the bots.

The first line contains two positive integers $n,q$. The next $q$ lines each describe an operation or query, in one of the following three forms: - `1 l r k`; - `2 l r k`; - `3`.

Output several lines, each answering one query of type 3.

### Explanation for Sample 1 Only operations 1 and 2 are explained. In the first operation, bots 3 and 4 drank 8 bottles of original-flavor iced black tea, and the other bots drank 8 bottles of tropical-flavor iced black tea. In the second operation, bots 3 and 4 had continuously drunk 8 bottles of original-flavor iced black tea, so they were destroyed. Now there are 3 bots alive. In the third operation, bot 2 drank 3 bottles of original-flavor iced black tea, and the other bots drank 3 bottles of tropical-flavor iced black tea. In the fourth operation, bots 1 and 5 had continuously drunk 11 bottles of tropical-flavor iced black tea, so they were destroyed. Now there is 1 bot alive. In the fifth operation, bot 2 drank 3 bottles of original-flavor iced black tea. In the sixth operation, bot 2 had continuously drunk 6 bottles of original-flavor iced black tea, so it was destroyed. Now there are no bots alive. ### Constraints **This problem uses bundled tests.** - Subtask 1 (5pts): $n,q\le 10^3$. - Subtask 2 (20pts): for all operations 2, $k\le 20$. - Subtask 3 (25pts): the testdata is guaranteed to be randomly generated. - Subtask 4 (50pts): no special constraints. The testdata generation method for Subtask 3 is as follows: 1. For each operation or query, choose one type from the three types with equal probability. 2. If the chosen type is not 3, then generate two numbers $l, r$ uniformly at random from $\left[1, n\right]$. If $l > r$, swap $l, r$, and use $l, r$ as the parameters of the operation. 3. If the chosen type is not 3, then generate a number $k$ uniformly at random from $\left[1, 10^6\right]$ as the parameter of the operation. For all data, it is guaranteed that $1\le n,q\le 2\times 10^5$ and $1\le k\le 10^{6}$. Translated by ChatGPT 5