Description

 

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

 

　　5种运算如下：

U T	S∪T
I T	S∩T
D T	S－T
C T	T－S
S T	S⊕T

 

　　基本集合运算如下：

A∪B	{x : xÎA or xÎB}
A∩B	{x : xÎA and xÎB}
A－B	{x : xÎA and xÏB}
A⊕B	(A－B)∪(B－A)

 

Input

　　输入共M行。

　　每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。

 

Output

 

　　共一行，即集合S，每个区间后面带一个空格。若S为空则输出"empty set"。

 

Sample Input

U [1,5]

D [3,3]

S [2,4]

C (1,5)

I (2,3]

Sample Output

(2,3)

HINT

对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000

---

题解Here!

 

很容易想到把区间转化成$01$序列来做。

但是开闭区间怎么办？

我们考虑这样一种变换：$[2,3)->[2,2.5],(3,4]->[2.5,4]$

那么把所有区间这样处理之后，再乘$2$，就是我们要处理的整数区间。

然后用线段树维护一下区间标记就好。

操作一是区间全改为$1$。

操作二是区间之外全改为$0$。

操作三是区间全改为$0$。

操作四是先将区间之外全改为$0$，然后将区间全部异或$1$。

操作五是区间全部异或$1$。

线段树乱搞搞事就好辣！

输出也很好搞，记录头尾$start,last$就好辣！

然后我调了一个下午，发现我这个沙茶把线段树的标记下传写错了。。。药丸。。。

附代码：

#include
      
       #include
       
        #include
        
         #define LSON rt<<1#define RSON rt<<1|1#define DATA(x) a[x].data#define SIGN(x) a[x].c#define REV(x) a[x].flag#define LSIDE(x) a[x].l#define RSIDE(x) a[x].r#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)#define MAXN 200010using namespace std;int n=(65536*2+1);struct Segment_Tree{	int data,c,flag;	int l,r;}a[MAXN<<2];inline int read(){	int date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}inline void pushup(int rt){	DATA(rt)=DATA(LSON)+DATA(RSON);}inline void pushdown(int rt){	if(LSIDE(rt)==RSIDE(rt))return;	if(SIGN(rt)!=-1){		REV(LSON)=0;SIGN(LSON)=SIGN(rt);		DATA(LSON)=SIGN(rt)*WIDTH(LSON);		REV(RSON)=0;SIGN(RSON)=SIGN(rt);		DATA(RSON)=SIGN(rt)*WIDTH(RSON);		SIGN(rt)=-1;	}	if(REV(rt)){		REV(LSON)^=1;		DATA(LSON)=WIDTH(LSON)-DATA(LSON);		REV(RSON)^=1;		DATA(RSON)=WIDTH(RSON)-DATA(RSON);		REV(rt)=0;	}}void buildtree(int l,int r,int rt){	LSIDE(rt)=l;RSIDE(rt)=r;SIGN(rt)=-1;REV(rt)=0;	if(l==r){		DATA(rt)=0;		return;	}	int mid=l+r>>1;	buildtree(l,mid,LSON);	buildtree(mid+1,r,RSON);	pushup(rt);}void update_rev(int l,int r,int rt){	if(l<=LSIDE(rt)&&RSIDE(rt)<=r){		REV(rt)^=1;		DATA(rt)=WIDTH(rt)-DATA(rt);		return;	}	pushdown(rt);	int mid=LSIDE(rt)+RSIDE(rt)>>1;	if(l<=mid)update_rev(l,r,LSON);	if(mid
         
          >1;	if(l<=mid)update_all(l,r,c,LSON);	if(mid
          
           >1;	if(l<=mid)ans+=query(l,r,LSON);	if(mid