3295. 集合维护

单点时限: 2.0 sec

内存限制: 256 MB

远岛子开始学习集合论了。

她知道了空集是不含有任何元素的集合,用 $\emptyset$ 表示。

满足 $0\leq x \leq 1$ 的数可以表示为$[0,1]$,满足 $0<x<1$ 的数可以表示为$(0,1)$。方括号包含端点被称为闭区间而圆括号不包含端点被称为开区间,相似的还有$(0,1],[0,1)$。

$A,B$两区间的交集指属于 $A$ 且属于 $B$ 的元素的区间,用 $A\cap B$ 表示,如:$(0,3]\cap (1,4]=(1,3]\quad (0,1)\cap (1,2)=\emptyset\quad [1,2]\cap [2,3]=[2,2]$

$A,B$ 两区间的并集指属于 $A$ 或属于 $B$ 的元素的区间,用 $A\cup B$ 表示,如:$[1,3]\cup [2,4]=[1,4]\quad (1,3)\cup [3,4)=(1,4)\quad (1,3)\cup (3,4)$

远岛子想要维护一个集合 $S$,$S$ 一开始是空集。定义两种操作第一种是1 P,表示 $S=S\cap P$,第二种是2 P,表示 $S=S\cup P$。$P$ 是一个区间。远岛子想要知道经过 $m$ 次操作后 $S$ 中含有什么。

输入格式

第一行为数据的组数 $T(T\leq 150)$

每组数据第一行为 $m$ 代表对 $S$ 操作的次数 $(m\leq 100)$

每次操作为1 P或者2 P分别代表交合并

$P$ 的格式为Ll,rRL,R([l,r 为整数 $(0\leq l\leq r\leq 100)$

保证$40\%$的数据只包含闭区间(包含端点的区间)且只含有并操作。

输出格式

每组数据输出一行,表示集合的情况

其中空集输出"empty set"

如果集合中有多段,使用U连接每段集合,代表并

集合以最少集合的并集输出

样例

Input
5
1
1 (1,2)
2
2 (1,2)
2 (2,3)
2
2 (1,2)
2 [2,3)
3
2 [2,3]
2 [4,5]
1 (2,5)
2
2 [1,3]
1 [3,4]
Output
empty set
(1,2)U(2,3)
(1,3)
(2,3]U[4,5)
[3,3]

4 人解决,13 人已尝试。

4 份提交通过,共有 33 份提交。

8.8 EMB 奖励。

创建: 3 年,2 月前.

修改: 3 年,1 月前.

最后提交: 2 年,5 月前.

来源: 2017.7.1 少年宫暑假摸底

题目标签