CF817F MEX Queries
题目描述
给定一个初始为空的整数集合。你需要依次执行 n 次查询,每次查询是以下三种类型之一:
∙类型 1:给定 l,r,将区间 [l,r] 内所有尚未被包含的整数加入集合;
∙类型 2:给定 l,r,将区间 [l,r] 内所有已被包含的整数从集合中删除;
∙类型 3:给定 l,r,翻转区间 [l,r],即把该区间内已被包含的整数删除,把该区间内未被包含的整数加入集合。
每次查询后,你需要输出当前集合的 mex,即最小的、不属于集合的正整数。
输入格式
第一行输入一个整数 n(1≦n≦105) 代表查询次数。
此后 n 行,第 i 行输入三个整数 $t,l,r\left(1 \leqq t \leqq 3;\ 1 \leqq l \leqq r \leqq 10^{18}\right)$ 代表第 i 次查询的类型与区间端点。
输出格式
对于每次查询,新起一行输出一个整数,代表该次查询结束后当前集合的 mex。
测试样例
3
1 3 4
3 1 6
2 1 3
1
3
1
样例 1 解释
初始时集合为空,每次查询后集合的内容与答案如下:
∙第 1 次查询为类型 1,区间 [3,4] 内的数尚未被包含,全部加入集合,集合变为 {3,4},mex=1;
∙第 2 次查询为类型 3,区间 [1,6] 内的 3,4 被删除,1,2,5,6 被加入,集合变为 {1,2,5,6},mex=3;
∙第 3 次查询为类型 2,删除区间 [1,3] 内的 1,2,集合变为 {5,6},mex=1。
4
1 1 3
3 5 6
2 4 4
3 1 6
4
4
4
1