3226. [SDOI2008]校门外的区间【线段树】

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<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  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<l1) return 0;
 41     if (l1<=l && r<=r1)
 42         return Segt[node].val;
 43     Pushdown(node,l,r);
 44     LL mid=(l+r)/2;
 45     return Query(node*2,l,mid,l1,r1)+Query(node*2+1,mid+1,r,l1,r1);
 46 }
 47 
 48 void Add(LL node,LL l,LL r,LL l1,LL r1,LL k)
 49 {
 50     if (l>r1 || r<l1) return;
 51     if (l1<=l && r<=r1)
 52     {
 53         Segt[node].val+=(r-l+1)*k;
 54         Segt[node].add+=k;
 55         return;
 56     }
 57     Pushdown(node,l,r);
 58     LL mid=(l+r)/2;
 59     Add(node*2,l,mid,l1,r1,k);
 60     Add(node*2+1,mid+1,r,l1,r1,k);
 61     Segt[node].val=Segt[node*2].val+Segt[node*2+1].val;
 62 }
 63 
 64 void Mul(LL node,LL l,LL r,LL l1,LL r1,LL k)
 65 {
 66     if (l>r1 || r<l1) return;
 67     if (l1<=l && r<=r1)
 68     {
 69         Segt[node].mul*=k;
 70         Segt[node].add*=k;
 71         Segt[node].val*=k;
 72         return;
 73     }
 74     Pushdown(node,l,r);
 75     LL mid=(l+r)/2;
 76     Mul(node*2,l,mid,l1,r1,k);
 77     Mul(node*2+1,mid+1,r,l1,r1,k);
 78     Segt[node].val=Segt[node*2].val+Segt[node*2+1].val;
 79 }
 80 
 81 void Init()
 82 {
 83     if (st[0]=='U') opt=1;
 84     if (st[0]=='I') opt=2;
 85     if (st[0]=='D') opt=3;
 86     if (st[0]=='C') opt=4;
 87     if (st[0]=='S') opt=5;
 88     cin>>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 }