P7505 "Wdsr-2.5" Tiny Haniwa Army

Zhang Dao Ou Mo Gong is the leader of the Haniwa army. As the Haniwa commander, training the Haniwa army is a very common task.

Mo Gong gives an order to make the Haniwa stand in a line. You may think they are standing on a number line, and each Haniwa’s position is the number on the number line under its feet. Mo Gong will tell you that the position of the $i$-th Haniwa is $a_i$. It is **not guaranteed** that $\bm {a_i}$ is in **increasing order**. The length of the number line is limited to the range $[-k, k]$. That is, if a Haniwa moves out of this range, it leaves the line, and will never return to the line again. To train the Haniwa, Mo Gong issues $m$ commands. There are 3 types: - Command 1: **All Haniwa** move $x$ units in the positive direction of the number line. - Command 2: **All Haniwa** move $x$ units in the negative direction of the number line. - Command 3: Call the roll in order, and count how many Haniwa are currently in the line. However, Mo Gong found that the Haniwa army is so large that performing these operations becomes very slow. Even so, Mo Gong still wants you to output the results of all Command 3.

The first line contains $3$ integers $n, m, k$, with meanings as described in the statement. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the positions of the Haniwa. The next $m$ lines each contain $1$ or $2$ positive integers describing one command. First is an integer $\operatorname{op}$ indicating the type of the command. If $1 \leq \operatorname{op} \leq 2$, then an integer $x$ is also given.

For each Command 3, output one integer: the number of Haniwa that are still in the line.

#### Explanation for Sample 1 There are three Haniwa in total. Initially, their positions are $[-1, 1, 2]$. - After the first operation, all Haniwa move left by $3$ units, and the positions become $[\underline{\bm{-4}}, -2, -1]$. The first Haniwa is moved out of the number line. - After the second operation, output the current number of Haniwa, which is $2$. - After the third operation, all Haniwa move right by $5$ units, and the positions become $[3, \underline{\bm4}]$. The second Haniwa is moved out of the number line. - After the fourth operation, output the current number of Haniwa, which is $1$. #### Samples 2 and 3 See the attached files provided. #### Constraints - For $30\%$ of the testdata, $1 \leq n, m \leq 5\times 10^3$. - For another $20\%$ of the testdata, $1 \le k \le 500$. - For $100\%$ of the testdata, $1 \leq n, m \leq 3\times 10^5$, $1 \leq k, x \leq 2 \times 10^9$, and $-k \le a_i \le k$. Translated by ChatGPT 5