T565371 「TFXOI R1」Doomsday

> Extinguished in radiance, disintegrated from order, vanished into ashes.

After the "God" created the "World", the "Demon" representing destruction and apocalypse descended upon it again. Initially, the "World" consists of $n$ **empty** "lands", with $V$ types of materials numbered from $0$. As "history" progresses, $m$ events occur during the battles between "God" and "Demon". As the "God's" agent, you observe these events from the clouds. Each event starts with a number $T$ and belongs to one of the following four types: 1. `0 l r`: Query the $mex$ (minimum excluded value) of all material types present in lands $[l, r]$. If all types appear, output $V$. 2. `1 op l r v`: - If $op=1$, "God" creates material $v$ on every land in $[l, r]$. - If $op=0$, "Demon" destroys all material $v$ on every land in $[l, r]$. 3. `2 op x`: - If $op=1$, "God" inserts an empty land before the $x$-th land. - If $op=0$, "Demon" permanently destroys the $x$-th land. 4. `3 l r v`: Convert every material $i$ (if exists) on lands $[l, r]$ to type $(i + v) \bmod V$. You must answer all queries of type $0$.

N/A

N/A

### Sample 1 Explanation Initial "World": $\{\varnothing,\varnothing,\varnothing,\varnothing,\varnothing\}$. After first event: $\{\{0\},\{0\},\{0\},\varnothing,\varnothing\}$. After second event: $\{\{0\},\{0,1\},\{0,1\},\{1\},\varnothing\}$. After third event: $\{\{0\},\{0,1\},\{0,1,2\},\{1,2\},\{2\}\}$. After fourth event: $\{\{0\},\{0,1\},\{1,2\},\{2\}\}$. Fifth query: In $\{\{0,1\},\{1,2\},\{2\}\}$, the smallest missing material is $3$, so output 3. ### Constraints - **Bundled testing is used**. - **Moderately tight time constraints**: optimize your code carefully. - For all data: $1 \le n, m \le 10^5$, $4 \le V \le 2^{10}$, $T \in \{0,1,2,3\}$, $op \in \{0,1\}$, $0 \le v < V$. All $l, r, x$ are valid positions in the current "World", and the "World" is never fully destroyed. Detailed constraints: | Subtask ID | $n, m$ | $V$ | Special Conditions | Points | |:-:|:-:|:-:|:-:|:-:| | #1 | $\le 3000$ | $=4$ | - | 10 pts | | #2 | $\le 3000$ | $=2^{10}$ | - | 10 pts | | #3 | - | $=4$ | $l = r$ | 15 pts | | #4 | - | $=2^{10}$ | $T \neq 2$ | 25 pts | | #5 | - | $=2^{10}$ | - | 40 pts | Translated by DeepSeek R1