Description

 

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

 

　　5种运算如下：

 

S∪T

S∩T

S－T

T－S

S⊕T

 

　　基本集合运算如下：

 

{x : xÎA or xÎB}

{x : xÎA and xÎB}

{x : xÎA and xÏ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

 

0代表没有，1代表有

U并：T区间*0 +1

I交：T区间外*0

D减：T区间*0

C(T-S)：T外面的*0，然后T*-1  +1

S：T区间-1 *-1

然后每个点拆成三个点，用来处理开区间和闭区间

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #define LL long long  5 #define N (300000)  6 using namespace std;  7 struct emm  8 {  9     LL val,add,mul; 10 }Segt[N*4]; 11 LL opt,x,y,n=300000; 12 char st[100]; 13  14 void Pushdown(LL node,LL l,LL r) 15 { 16     if (Segt[node].mul!=1) 17     { 18         Segt[node*2].mul*=Segt[node].mul; 19         Segt[node*2+1].mul*=Segt[node].mul; 20         Segt[node*2].add*=Segt[node].mul; 21         Segt[node*2+1].add*=Segt[node].mul; 22          23         Segt[node*2].val*=Segt[node].mul; 24         Segt[node*2+1].val*=Segt[node].mul; 25         Segt[node].mul=1; 26     } 27     if (Segt[node].add!=0) 28     { 29         Segt[node*2].add+=Segt[node].add; 30         Segt[node*2+1].add+=Segt[node].add; 31         LL mid=(l+r)/2; 32         Segt[node*2].val+=(mid-l+1)*Segt[node].add; 33         Segt[node*2+1].val+=(r-mid)*Segt[node].add; 34         Segt[node].add=0; 35     } 36 } 37  38 LL Query(LL node,LL l,LL r,LL l1,LL r1) 39 { 40     if (l>r1 || r
        
         r1 || r
         
          r1 || r
          
           >st; 89 x=0,y=0; 90 LL s=1; 91 while (1) 92 { 93 if (st[s]==',') break; 94 x=x*10+st[s]-'0'; s++; 95 } 96 for (LL i=s+1;i<=strlen(st)-2;++i) 97 y=y*10+st[i]-'0'; 98 x=x*3+2; 99 if (st[0]=='(') x++;100 y=y*3+2;101 if (st[strlen(st)-1]==')') y--;102 }103 104 void print()105 {106 bool flag=false,refun=false;107 LL i=1;108 while (i<=n)109 {110 if (!flag && (i-1)%3+1>=2 && Query(1,1,n,i,i)>0)111 {112 flag=true;refun=true;113 if ((i-1)%3+1==2) cout<<'['; else cout <<'(';114 cout<<(i-1)/3<<',';115 }116 if (flag && Query(1,1,n,i,i)<=0)117 {118 flag=false;refun=true;119 cout<<(i-2)/3;120 if ((i-2)%3+1>=2) cout<<"] "; else cout <<") ";121 }122 ++i;123 }124 if (!refun) cout<<"empty set";125 }126 127 int main()128 {129 for (LL i=1;i<=n*4;++i) Segt[i].mul=1;130 LL i=0;131 while (cin>>st)132 {133 Init();134 i++;135 if (opt==1) Mul(1,1,n,x,y,0),Add(1,1,n,x,y,1);136 if (opt==2) Mul(1,1,n,1,x-1,0),Mul(1,1,n,y+1,n,0);137 if (opt==3) Mul(1,1,n,x,y,0);138 if (opt==4) Mul(1,1,n,1,x-1,0),Mul(1,1,n,y+1,n,0),Mul(1,1,n,x,y,-1),Add(1,1,n,x,y,1);139 if (opt==5) Add(1,1,n,x,y,-1),Mul(1,1,n,x,y,-1); 140 }141 print();142 }