题意：区间交、并、减、补
思路：用线段树的叶子节点记录该点是否被区间覆盖，因为有开区间的情况，因此考虑离散，将数值乘以2。
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
区间修改容易做，但是加上区间异或就难了。
我们考虑维护这样一棵线段树，如果区段的setv不是-1(初始化时候为-1)，则说明该节点所对应的区段内全部的值为setv，如果根节点和子节点的setv值都不为-1，我们只认根节点上面的setv值。然后维护一个xorv值，表示该节点对应区段是否被异或奇数次(异或偶数次和没异或一样，是0)。这个xorv值一定出现在查找时第一次遇到setv值的前面，也就是说，查找时会先遇到有意义的xorv值，再遇到有意义的setv值(有意义是指，xorv=1，或者setv!=-1)。当要修改某个区段或寻找某个区段的过程中，xorv值和setv值会用pushdown不断往下压。明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了。所以当一个节点得到覆盖标记时把异或标记清空托福答案
而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记托福改分
输出的时候，我们可以用一个hash数组记录，用一个query将线段树上的值往下压到hash数组里面。
注意几个问题：1.出现0的情况
2.(3,3)这种空集的情况
#include<cstdio>
#include<cstring>
#define M ((L+R)>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls,L,M
#define rson rs,M+1,R
const int maxn=66666*2;
bool hash[maxn],empty=1,flag=0;
int n,yl,yr,v,setv[maxn*4],xorv[maxn*4],a,b,low=0,high;
char op,left,right;
void fxor(int o) {if(setv[o]>=0) setv[o]^=1; else xorv[o]^=1;}
void pushdown(int o)
{
if(setv[o]>=0) {setv[ls]=setv[rs]=setv[o];xorv[ls]=xorv[rs]=0;setv[o]=-1;}
if(xorv[o])
{
fxor(ls);
fxor(rs);
xorv[o]=0;
}
}
void setupdate(int o,int L,int R)
{
if(yl<=L && R<=yr) {xorv[o]=0;setv[o]=v;return;}
pushdown(o);
if(yl<=M) setupdate(lson);
if(M<yr) setupdate(rson);
}
void xorupdate(int o,int L,int R)
{
if(yl<=L && R<=yr){fxor(o);return;}
pushdown(o);
if(yl<=M) xorupdate(lson);
if(M<yr) xorupdate(rson);
}
void query(int o,int L,int R)
{
if(setv[o]>=0)
{
if(setv[o]) for(int i=L;i<=R;++i) hash[i]=1;//将信息压倒hash里面去
return;
}
pushdown(o);
if(yl<=M) query(lson);
if(M<yr) query(rson);
}
void init()
{
memset(setv,-1,sizeof(setv));
memset(hash,0,sizeof(hash));
xorv[1]=setv[1]=0;
}
void read()
{
while(~scanf("%c %c%d,%d%c ",&op,&left,&a,&b,&right))
{
a=(a+1)*2,b=(b+1)*2;
if(left=='(') ++a; if(right==')') --b;
if(op=='U')
{
v=1,yl=a,yr=b;
if(yl<=yr) setupdate(1,1,maxn-1);
}
else if(op=='I')
{
v=0,yl=1,yr=a-1;
if(yl<=yr) setupdate(1,1,maxn-1);
yl=b+1,yr=maxn-1;
if(yl<=yr) setupdate(1,1,maxn-1);
}
else if(op=='D')
{
v=0,yl=a,yr=b;
if(yl<=yr) setupdate(1,1,maxn-1);
}
else if(op=='C')
{
v=0,yl=1,yr=a-1;
if(yl<=yr) setupdate(1,1,maxn-1);
yl=b+1,yr=maxn-1;
if(yl<=yr) setupdate(1,1,maxn-1);
yl=a,yr=b;
if(yl<=yr) xorupdate(1,1,maxn-1);
}
else if(op=='S')
{
yl=a,yr=b;
if(yl<=yr) xorupdate(1,1,maxn-1);
}
}
}
void print()
{
yl=1,yr=maxn-1;
query(1,1,maxn-1);
while(low<maxn)
{
while(!hash[low] && low<maxn) ++low;
high=low+1;
while(hash[high] && high<maxn) ++high;
--high;
if(low>=maxn) break;
empty=0;
if(flag) printf(" ");
flag=1;
if(low&1) printf("(");
else printf("[");
printf("%d,%d",(low/2)-1,(high-1)/2);
if(high&1) printf(")");
else printf("]");
low=high+1;
}
if(empty) printf("empty set");
puts("");
}
int main()
{
init();
read();
print();
return 0;
}