P8582 [CoE R5] Zebra Prince

#### Note: In Subtask #4 of this problem, $opt_i=3$ can be treated as $opt_i=0$. The testdata will be fixed later, and another notice will be given after the fix. #### UPD: Fixed.

**Brief statement** There is an array $s$ of length $k+1$, indexed from $0$ to $k$. Initially, $s_i = 0 \ (0 \leqslant i \leqslant k)$. Next, you are given $n$ pairs of non-negative integers $(l_i,\ r_i)$. Let $T = \bigcup\limits_{i = 1}^n [l_i,\ r_i]$. Set all $s_i$ with $i \in T \bigcap \mathbb{Z}$ to $1$. At any moment, define $S =\{ x \mid x \in \mathbb{Z} \wedge x \in [0,\ k] \wedge s_x = 0 \}$. Then you are given $m$ triples of non-negative integers $(opt_i,\ a_i,\ b_i)$. - When $opt_i = 0$, compute: $$t_i = \sum\limits_{x = a_i}^{b_i} \min\limits_{y \in S}(x \oplus y)$$ - When $opt_i = 1$, set all $s_i$ with $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ to $1$. - When $opt_i = 2$, set all $s_i$ with $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ to $0$. Here, $\mathbb{Z}$ denotes the set of all integers, and $\oplus$ denotes XOR. --- **Original story statement** The “Zebra Prince” rules over the boundless grassland. A small river flows quietly through the center of the grassland. A piece of grassland at distance $y$ from the river source is given “membrane power” (mo li, 膜力) of value $y \ (0 \leqslant y \leqslant k)$. On day $x \ (0 \leqslant x \leqslant k)$, the Zebra Prince’s “potential IQ” is $x$. He will go to a grassland he likes to dine, and start a new day with “IQ” equal to $x \oplus y$. There is a kind of creature called “hunters”, who love to take away the lives of grassland residents. Initially, they set up $n$ camps of the form $(l_i,\ r_i) \ (0 \leqslant l_i \leqslant r_i \leqslant k)$, and use “guns” to kill all living beings that stop within $[l_i,\ r_i]$. As the Zebra Prince’s capable minister, you need to answer some of his questions to keep the grassland safe. On this ever-changing grassland, $m$ events of the form $(opt_i,\ a_i,\ b_i) \ (0 \leqslant a_i \leqslant b_i \leqslant k , \ opt_i \in \{0,\ 1,\ 2\})$ will happen in order. When $opt_i = 1$, event $i$ means the hunters have set up new camps everywhere in $[a_i,\ b_i]$. When $opt_i = 2$, event $i$ means the Zebra Prince’s brave army has destroyed all camps in $[a_i,\ b_i]$. When $opt_i = 0$, the Zebra Prince asks you a soul-searching question: In each query, from day $a_i$ to day $b_i$ $(0 \leqslant a_i \leqslant b_i \leqslant k)$, the Zebra Prince wants to dine on grasslands that are not “hunter” camps. He wants to know the minimum possible value $t_i$ of the sum of “IQ” from day $a_i$ to day $b_i$. You rack your brain. Suddenly, the roar of “guns” tears the air apart. If you cannot answer within $1 \ sec$…

The first line contains integers $n, \ m, \ k$. The next $n$ lines each contain two integers $l_i, \ r_i$, describing one hunter camp. The next $m$ lines each contain three integers $opt_i,\ a_i,\ b_i$, describing one operation.

For the $i$-th operation $(1 \leqslant i \leqslant m)$: - If $opt_i = 1$ or $opt_i = 2$, you do not need to output anything. - If $opt_i = 0$, then if all grasslands belong to hunter camps, output one line `Death`. Otherwise, output one line with an integer, representing $t_i$.

**Constraints** **This problem uses bundled tests.** $\texttt{Subtask 1 (5 pts)}$: For $5\%$ of the data, $0 \leqslant n,m,k \leqslant 20$. $\texttt{Subtask 2 (5 pts)}$: For $5\%$ of the data, $0 \leqslant n,m,k \leqslant 500$. $\texttt{Subtask 3 (15 pts)}$: For $15\%$ of the data, $0 \leqslant n,m,k \leqslant 4000$. $\texttt{Subtask 4 (5 pts)}$: For $5\%$ of the data, $opt_i = 0$. $\texttt{Subtask 5 (70 pts)}$: No special restrictions. For $100\%$ of the data: $0 \leqslant n,\ m,\ k \leqslant 2 \times 10^5$, $0 \leqslant l_i \leqslant r_i \leqslant k$, $0 \leqslant a_i \leqslant b_i \leqslant k$, and $opt_i \in \{0,\ 1,\ 2\}$. Translated by ChatGPT 5