3851 - 校门外的区间
受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出5种运算维护集合S(S初始为空)并最终输出S。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
5种运算如下：
|
U T
|
S∪T
|
|
I T
|
S∩T
|
|
D T
|
S－T
|
|
C T
|
T－S
|
|
S T
|
S⊕T
|
基本集合运算如下：
|
A∪B
|
{x : xÎA or xÎB}
|
|
A∩B
|
{x : xÎA and xÎB}
|
|
A－B
|
{x : xÎA and xÏB}
|
|
A⊕B
|
(A－B)∪(B－A)
|
Input
输入共M行。
每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。
Output
共一行，即集合S，每个区间后面带一个空格。若S为空则输出”empty set”。
Examples
Input
U [1,5] D [3,3] S [2,4] C (1,5) I (2,3]
Output
(2,3)
Hint
对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000
Solution C++
//SegTree & Lazy_Mark by stdafx. // [0,65535] #define cson l,r,rt #define lson l,m,t #define rson m+1,r,t|1 #define MAXN 65540UL #define MAXL 20UL #include <cstdio> #include <queue> std::queue<int> que; int tree[MAXN<<2],posl,posr,tp,mark[MAXN<<2]; bool final[MAXN][2]; char op[MAXL],interval[MAXL]; inline void Clear_mark(int l,int r,int rt){ if(!mark[rt]||l==r) return; int t=rt<<1; if(mark[rt]==1||mark[rt]==2){ mark[t]=mark[t|1]=mark[rt]; } else{ if(mark[t]==1) mark[t]=2; else if(mark[t]==2) mark[t]=1; else if(mark[t]==3) mark[t]=0; else mark[t]=3; t|=1; if(mark[t]==1) mark[t]=2; else if(mark[t]==2) mark[t]=1; else if(mark[t]==3) mark[t]=0; else mark[t]=3; } mark[rt]=0; return; } inline void Update_mark(int l,int r,int rt){ Clear_mark(cson); if(posl<=l&&posr>=r){ //printf("[%d,%d] r=%d\n",l,r,mark[rt]); if(tp==1||tp==2){ mark[rt]=tp; } else{ if(mark[rt]==1) mark[rt]=2; else if(mark[rt]==2) mark[rt]=1; else if(mark[rt]==3) mark[rt]=0; else mark[rt]=3; } //printf("Change to %d\n",mark[rt]); return; } int m=(l+r)>>1,t=rt<<1; if(posl<=m) Update_mark(lson); if(posr>m) Update_mark(rson); return; } inline void UPDATE_MARK(int l,int r,int t){ if(l>r) return; posl=l,posr=r,tp=t; Update_mark(0,65536,1);return; } inline void Work_Ingter(int l,int r){ //printf("%d %d\n",l,r); if(l>r) return; if(op[0]=='U') UPDATE_MARK(l,r,1); else if(op[0]=='I') UPDATE_MARK(0,l-1,2),UPDATE_MARK(r+1,65536,2); else if(op[0]=='D') UPDATE_MARK(l,r,2); else if(op[0]=='C') UPDATE_MARK(0,l-1,2),UPDATE_MARK(r+1,65536,2),UPDATE_MARK(l,r,3); else if(op[0]=='S') UPDATE_MARK(l,r,3); return; } inline void Read(int &l,int &r){ int p=1;l=r=0; for(/**/;interval[p]<='9'&&interval[p]>='0';p++) l=(l<<1)+(l<<3)+interval[p]-48; for( p++;interval[p]<='9'&&interval[p]>='0';p++) r=(r<<1)+(r<<3)+interval[p]-48; int new_l=l,new_r=r; if(interval[0]=='(') new_l++; if(interval[p]==')') new_r--; Work_Ingter(new_l,new_r); r--; return; } inline void Clear(int l,int r,int rt){ if(!tree[rt]||l==r) return; int t=rt<<1; if(tree[rt]==1||tree[rt]==2){ tree[t]=tree[t|1]=tree[rt]; } else{ if(tree[t]==1) tree[t]=2; else if(tree[t]==2) tree[t]=1; else if(tree[t]==3) tree[t]=0; else tree[t]=3; t|=1; if(tree[t]==1) tree[t]=2; else if(tree[t]==2) tree[t]=1; else if(tree[t]==3) tree[t]=0; else tree[t]=3; } tree[rt]=0; return; } inline void Update(int l,int r,int rt){ Clear(cson); if(posl<=l&&posr>=r){ if(tp==1||tp==2){ tree[rt]=tp; } else{ if(tree[rt]==1) tree[rt]=2; else if(tree[rt]==2) tree[rt]=1; else if(tree[rt]==3) tree[rt]=0; else tree[rt]=3; } return; } int m=(l+r)>>1,t=rt<<1; if(posl<=m) Update(lson); if(posr>m) Update(rson); return; } inline void UPDATE(int l,int r,int t){ if(l>r) return; posl=l,posr=r,tp=t; Update(0,65536,1);return; } inline void Build(int l,int r,int rt){ Clear(cson); Clear_mark(cson); if(l==r){ //if(l<10) printf("%d %d %d\n",l,tree[rt],mark[rt]); if(tree[rt]==1||tree[rt]==3) final[l][0]=true; if(mark[rt]==1||mark[rt]==3) final[l][1]=true; return; } int m=(l+r)>>1,t=rt<<1; Build(lson);Build(rson); return; } inline void Work(){ int l,r;Read(l,r); if(op[0]=='U') UPDATE(l,r,1); else if(op[0]=='I') UPDATE(0,l-1,2),UPDATE(r+1,65536,2); else if(op[0]=='D') UPDATE(l,r,2); else if(op[0]=='C') UPDATE(0,l-1,2),UPDATE(r+1,65536,2),UPDATE(l,r,3); else if(op[0]=='S') UPDATE(l,r,3); //Build(1,65536,1); return; } //1 -> true //2 -> false //3 -> change int main(){ while(~scanf("%s%s",op,interval)) Work(); Build(0,65536,1); bool pt=false; for(int i=0;i<=65537;i++){ int r=i; if(!final[i][0]){ if(final[i][1]) printf("[%d,%d] ",i,i),pt=true; } while(final[r][0]) r++; if(i==r) continue; pt=true; if(final[i][1]) printf("["); else printf("("); printf("%d,%d",i,r); if(final[r][1]) printf("] "); else printf(") ");i=r; } if(!pt) puts("empty set"); return 0; }
Hint
对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000