maxmex

题目描述

有 $n$ 个集合 $S_0,S_1 \cdots S_{n-1}$。最初，集合全都为空。

在线执行 $m$ 次操作，每次操作是以下两种之一：

• $1$，$x$，$l$，$r$：$\forall i \in [l,r]$，若 $x \notin S_i$，将 $x$ 加入集合 $S_i$。
• $2$，$l$，$r$：查询 $\max_{i \in [l,r]} \texttt{mex}(S_i)$。集合的 $\texttt{mex}$ 定义为最小的不在集合内的自然数。

输入格式

第一行输入三个数 $n,m,op$。其中 $op \in \{0,1\}$ 为是否进行了加密。

接下来 $m$ 行，按照格式输入操作。

若 $op=1$，则需要对首次询问之后输入的所有 $l,r,x$ 都异或上一次询问的答案，才是真实值。

输出格式

对于每个询问输出一行一个数表示答案。

输入 #1

10 10 0
1 0 1 1
2 0 9
1 0 8 8
1 1 1 5
1 1 7 9
2 3 6
1 0 4 4
2 3 4
1 2 3 6
2 3 6

输出 #1

1
0
2
3

说明/提示

对于所有数据：

$1 \le n,m \le 5 \times 10^5$。保证两操作的数量相等。

$0 \le l \le r < n$。

$0 \le x < m$。

子任务 1（5分）：$n,m \le 5000$。

子任务 2（15分）：修改全部在询问之前。

子任务 3（20分）：$n,m \le 50000$，$op=0$。

子任务 4（20分）：$op=0$。

子任务 5（20分）：$n,m \le 50000$。

子任务 6（20分）：无特殊性质。