细节处理实在太重要了。
#include<cstdio>
#include<cstring>
#define MT 65533*4
#define Maxn MT*4
int i,x,y,now,k;
int xo[Maxn],e[Maxn],pd[MT];
char a,b,c;
inline void work(int k,int rt){
if(k<2){
xo[rt]=0;
e[rt]=k;
}else{
if(e[rt]>-1)
e[rt]^=1;
else
xo[rt]^=1;
}
}
void PushDown(int rt){
if(e[rt]>-1){
e[rt*2+1]=e[rt*2]=e[rt];
e[rt]=-1;
}
else{
if(e[rt*2]>-1) {e[rt*2]^=xo[rt]; xo[rt*2]=0;}
else xo[rt*2]^=xo[rt];
if(e[rt*2+1]>-1) {e[rt*2+1]^=xo[rt];xo[rt*2+1]=0;}
else xo[rt*2+1]^=xo[rt];
}
xo[rt]=0;
}
void ins(int k,int x,int y,int l,int r,int rt){
if(x<=l&&y>=r){
work(k,rt);
return;
}
PushDown(rt);
int m=(l+r)/2;
if(x<=m) ins(k,x,y,l,m,rt*2);
if(y>m) ins(k,x,y,m+1,r,rt*2+1);
}
void query(int l,int r,int rt){
if(e[rt]==1) {
for(int i=l;i<=r;i++)
pd[i]=1;
return;
}
if(e[rt]==0) return;
if(l>=r) return;
PushDown(rt);
int m=(l+r)/2;
query(l,m,rt*2);
query(m+1,r,rt*2+1);
}
int main()
{
while(scanf("%c %c%d,%d%c\n",&a,&b,&x,&y,&c)!=EOF){
if(b=='[') x=2*x; else x=2*x+1;
if(c==']') y=2*y; else y=2*y-1;
switch (a){
case 'U':
ins(1,x,y,0,MT,1);
break;
case 'I':
ins(0,0,x-1,0,MT,1);
ins(0,y+1,MT,0,MT,1);
break;
case 'D':
ins(0,x,y,0,MT,1);
break;
case 'C':
ins(0,0,x-1,0,MT,1);
ins(0,y+1,MT,0,MT,1);
ins(2,x,y,0,MT,1);
break;
case 'S':
ins(2,x,y,0,MT,1);
break;
}
}
query(0,MT,1);
k=0;
for(i=0;i<MT;i++)
if(1==pd[i]){
if(0==i||pd[i-1]==0){
if(i%2==0) printf("[%d",i/2);
else printf("(%d",(i-1)/2);
}
if(MT-1==i||pd[i+1]==0){
if(i%2==0) printf(",%d] ",i/2);
else printf(",%d) ",(i+1)/2);
}
k=1;
}
if(!k) printf("empty set\n");
return 0;
}