#P3226. [Sdoi2008]校门外的区间

    ID: 2411 传统题 1000ms 512MiB 尝试: 1527 已通过: 387 难度: 6 上传者: 标签>难度分类提高模拟与实现技巧坐标变换数据结构懒标记线段树标记复合CF2000

[Sdoi2008]校门外的区间

[SDOI2008] 校门外的区间

题目描述

受校门外的树这道经典问题的启发,A君根据基本的离散数学的知识,抽象出 55 种运算维护集合 SS (SS 初始为空)并最终输出 SS。现在,请你完成这道校门外的树之难度增强版——校门外的区间。

五种运算如下:

  • U T:S=S∪TS = S \cup T
  • I T:S=S∩TS = S \cap T
  • D T:S=S−TS = S - T
  • C T:S=T−SS = T - S
  • S T:S=S⊕TS = S \oplus T

集合的基本运算操作定义如下:

  • A∪BA \cup B:{x∣x∈A∨x∈B}\{x\mid x \in A \vee x \in B\}
  • A∩BA \cap B:{x∣x∈A∧x∈B}\{x\mid x \in A \wedge x \in B\}
  • A−BA - B:{x∣x∈A∧x∉B}\{x\mid x \in A \wedge x \notin B\}
  • A⊕BA \oplus B:(A−B)∪(B−A)(A-B)\cup (B-A)

输入格式

输入共 MM 行操作,读至文件结束。每行第一个字母描述操作类型,后面给出一个区间(区间用 (a,b),(a,b],[a,b),[a,b] 表示)。

输出格式

输出一行,将集合 SS 表示为若干不能再合并的实数区间。区间按左端点递增排列,相邻两段之间以一个空格分隔。

如果集合 SS 为空,输出 empty set。

样例 #1

样例输入 #1

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

样例输出 #1

(2,3)

提示

0≤a,b≤65535,M≤70000 0 \leq a,b \leq 65535, M \leq 70000