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]
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
然后每个点拆成三个点，用来处理开区间和闭区间
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
#define N (300000)
using namespace std;
struct emm
{
LL val,add,mul;
}Segt[N*];
LL opt,x,y,n=;
char st[]; void Pushdown(LL node,LL l,LL r)
{
if (Segt[node].mul!=)
{
Segt[node*].mul*=Segt[node].mul;
Segt[node*+].mul*=Segt[node].mul;
Segt[node*].add*=Segt[node].mul;
Segt[node*+].add*=Segt[node].mul; Segt[node*].val*=Segt[node].mul;
Segt[node*+].val*=Segt[node].mul;
Segt[node].mul=;
}
if (Segt[node].add!=)
{
Segt[node*].add+=Segt[node].add;
Segt[node*+].add+=Segt[node].add;
LL mid=(l+r)/;
Segt[node*].val+=(mid-l+)*Segt[node].add;
Segt[node*+].val+=(r-mid)*Segt[node].add;
Segt[node].add=;
}
} LL Query(LL node,LL l,LL r,LL l1,LL r1)
{
if (l>r1 || r<l1) return ;
if (l1<=l && r<=r1)
return Segt[node].val;
Pushdown(node,l,r);
LL mid=(l+r)/;
return Query(node*,l,mid,l1,r1)+Query(node*+,mid+,r,l1,r1);
} void Add(LL node,LL l,LL r,LL l1,LL r1,LL k)
{
if (l>r1 || r<l1) return;
if (l1<=l && r<=r1)
{
Segt[node].val+=(r-l+)*k;
Segt[node].add+=k;
return;
}
Pushdown(node,l,r);
LL mid=(l+r)/;
Add(node*,l,mid,l1,r1,k);
Add(node*+,mid+,r,l1,r1,k);
Segt[node].val=Segt[node*].val+Segt[node*+].val;
} void Mul(LL node,LL l,LL r,LL l1,LL r1,LL k)
{
if (l>r1 || r<l1) return;
if (l1<=l && r<=r1)
{
Segt[node].mul*=k;
Segt[node].add*=k;
Segt[node].val*=k;
return;
}
Pushdown(node,l,r);
LL mid=(l+r)/;
Mul(node*,l,mid,l1,r1,k);
Mul(node*+,mid+,r,l1,r1,k);
Segt[node].val=Segt[node*].val+Segt[node*+].val;
} void Init()
{
if (st[]=='U') opt=;
if (st[]=='I') opt=;
if (st[]=='D') opt=;
if (st[]=='C') opt=;
if (st[]=='S') opt=;
cin>>st;
x=,y=;
LL s=;
while ()
{
if (st[s]==',') break;
x=x*+st[s]-''; s++;
}
for (LL i=s+;i<=strlen(st)-;++i)
y=y*+st[i]-'';
x=x*+;
if (st[]=='(') x++;
y=y*+;
if (st[strlen(st)-]==')') y--;
} void print()
{
bool flag=false,refun=false;
LL i=;
while (i<=n)
{
if (!flag && (i-)%+>= && Query(,,n,i,i)>)
{
flag=true;refun=true;
if ((i-)%+==) cout<<'['; else cout <<'(';
cout<<(i-)/<<',';
}
if (flag && Query(,,n,i,i)<=)
{
flag=false;refun=true;
cout<<(i-)/;
if ((i-)%+>=) cout<<"] "; else cout <<") ";
}
++i;
}
if (!refun) cout<<"empty set";
} int main()
{
for (LL i=;i<=n*;++i) Segt[i].mul=;
LL i=;
while (cin>>st)
{
Init();
i++;
if (opt==) Mul(,,n,x,y,),Add(,,n,x,y,);
if (opt==) Mul(,,n,,x-,),Mul(,,n,y+,n,);
if (opt==) Mul(,,n,x,y,);
if (opt==) Mul(,,n,,x-,),Mul(,,n,y+,n,),Mul(,,n,x,y,-),Add(,,n,x,y,);
if (opt==) Add(,,n,x,y,-),Mul(,,n,x,y,-);
}
print();
}