#P3225. 区间

区间

Description

LogLoader是一家专门提供日志分析产品的公司。Ikki在做毕业设计的同时,还忙于在LogLoader做实习。在他的工作里,有一项是要写一个模块来处理时间区间。这个事情一直让他感到很迷糊,所以现在他很需要你帮忙。

在离散数学里面,你已经学习了几种基本的集合运算,具体地说就是并、交、相对补和对称差。它们自然地也适用于区间这种特殊的集合。作为你的快速参考,它们可以总结成下表:

运算记号

定义

AB{x : xAxB}
AB{x : xAxB}
相对补AB{x : xA但是B}
对称差AB(AB) ∪ (BA)

Ikki已经把他的工作里出现的区间运算抽象成一个很小的编程语言。他想你为他实现一个解析器。这个语言维护一个集合SS一开始是空集,并根据下列命令被修改:

命令语义
U TSST
I TSST
D TSST
C TSTS
S TSST

Input

输入包含一组测试数据,由0到65,535条命令组成。每条命令占一行,形式如下:

X T

其中X是‘U’、‘I’、‘D’、‘C’和‘S’中的一个,T是一个区间形式为(a,b)(a,b][a,b)[a,b]之一(a, bZ; 0 ≤ ab ≤ 65,535),取它们通常的意义。命令按在输入中出现的顺序执行。

文件结束符(EOF)表示输入结束。

Output

以一组不相交区间的并的形式输出在最后一条命令执行之后的集合S。这些区间在一行内输出,由单个空格分隔,按端点的升序排序。如果S是空集,输出“empty set”。

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

Source

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛

, frkstyc

Translator

Yingchong SITU 'frkstyc'