#CF817F. MEX 询问

MEX 询问

CF817F MEX Queries

题目描述

\hspace{15pt}给定一个初始为空的整数集合。你需要依次执行 nn 次查询,每次查询是以下三种类型之一:

∙ \hspace{23pt}\bullet\,类型 11:给定 l,rl,r,将区间 [l,r]\left[l,r\right] 内所有尚未被包含的整数加入集合;

∙ \hspace{23pt}\bullet\,类型 22:给定 l,rl,r,将区间 [l,r]\left[l,r\right] 内所有已被包含的整数从集合中删除;

∙ \hspace{23pt}\bullet\,类型 33:给定 l,rl,r,翻转区间 [l,r]\left[l,r\right],即把该区间内已被包含的整数删除,把该区间内未被包含的整数加入集合。

\hspace{15pt}每次查询后,你需要输出当前集合的 mex\mathrm{mex},即最小的、不属于集合的正整数。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n\left(1 \leqq n \leqq 10^5\right) 代表查询次数。

\hspace{15pt}此后 nn 行,第 ii 行输入三个整数 $t,l,r\left(1 \leqq t \leqq 3;\ 1 \leqq l \leqq r \leqq 10^{18}\right)$ 代表第 ii 次查询的类型与区间端点。

输出格式

\hspace{15pt}对于每次查询,新起一行输出一个整数,代表该次查询结束后当前集合的 mex\mathrm{mex}。

测试样例

3
1 3 4
3 1 6
2 1 3
1
3
1

样例 1 解释

\hspace{15pt}初始时集合为空,每次查询后集合的内容与答案如下:

∙ \hspace{23pt}\bullet\,第 11 次查询为类型 11,区间 [3,4]\left[3,4\right] 内的数尚未被包含,全部加入集合,集合变为 {3,4}\{3,4\},mex=1\mathrm{mex}=1;

∙ \hspace{23pt}\bullet\,第 22 次查询为类型 33,区间 [1,6]\left[1,6\right] 内的 3,43,4 被删除,1,2,5,61,2,5,6 被加入,集合变为 {1,2,5,6}\{1,2,5,6\},mex=3\mathrm{mex}=3;

∙ \hspace{23pt}\bullet\,第 33 次查询为类型 22,删除区间 [1,3]\left[1,3\right] 内的 1,21,2,集合变为 {5,6}\{5,6\},mex=1\mathrm{mex}=1。

4
1 1 3
3 5 6
2 4 4
3 1 6
4
4
4
1