P5568 [SDOI2008] Intervals Outside the School Gate

Inspired by the classic problem “Trees Outside the School Gate”, person A, based on basic knowledge of discrete mathematics, abstracts $5$ kinds of operations to maintain a set $S$ ($S$ is initially empty) and finally output $S$. Now, please complete this harder enhanced version of “Trees Outside the School Gate” — “Intervals Outside the School Gate”. The five operations are: - `U T`: $S = S \cup T$ - `I T`: $S = S \cap T$ - `D T`: $S = S - T$ - `C T`: $S = T - S$ - `S T`: $S = S \oplus T$ The basic set operations are defined as follows: - $A \cup B$: $\{x \mid x \in A \vee x \in B\}$ - $A \cap B$: $\{x \mid x \in A \wedge x \in B\}$ - $A - B$: $\{x \mid x \in A \wedge x \notin B\}$ - $A \oplus B$: $(A-B)\cup (B-A)$.

There are $M$ lines. The first letter of each line describes the operation type, followed by an interval (an interval is written as `(a,b)`, `(a,b]`, `[a,b)`, `[a,b]`).

Output one line containing several intervals representing the set $S$. **All intervals should be output in increasing order, and there should be exactly one space between two adjacent intervals**. If the set is empty, output `empty set`.

$0 \leq a,b \leq 65535, M \leq 70000$. Translated by ChatGPT 5