题目大意：
有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)
思路：
每个数之间加入一个数,就像这样2 2.5 3 3.5 4 [2,3) -> [2,2.5] (3,4] -> [3.5,4] 用01表示集合，则U 区间涂1；I 两侧区间涂0；D 区间涂0；C 两侧涂0,中间取反；S 区间取反。用线段树解决，标记的下传很重要（被坑了）。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define n 131073 4 using namespace std; 5 6 int lazy[n<<2],num[n<<2],rev[n<<2]; 7 8 int read() 9 { 10 int x=0,y=0; 11 char ch=getchar(); 12 while (ch<'0' || ch>'9') 13 { 14 if (ch=='(') y=1; 15 ch=getchar(); 16 } 17 while (ch>='0' && ch<='9') 18 { 19 x=x*10+ch-48; 20 ch=getchar(); 21 } 22 if (ch==')') y=-1; 23 return x*2+y+2; 24 } 25 26 void push_down(int x,int l,int r) 27 { 28 int y=lazy[x],z=rev[x]; 29 lazy[x]=-1,rev[x]=0; 30 if (l==r) 31 { 32 if (y!=-1) num[x]=y; 33 num[x]^=z; 34 return; 35 } 36 if (y!=-1) 37 { 38 lazy[x<<1]=lazy[x<<1|1]=y; 39 rev[x<<1]=rev[x<<1|1]=0; 40 } 41 rev[x<<1]^=z,rev[x<<1|1]^=z; 42 } 43 44 void add(int L,int R,int l,int r,int cur,int val) 45 { 46 if (l>r) return; 47 push_down(cur,L,R); 48 if (l<=L && r>=R) 49 { 50 if (val<2) lazy[cur]=val; 51 else rev[cur]^=1; 52 return; 53 } 54 int mid=L+R>>1; 55 if (l>mid) add(mid+1,R,l,r,cur<<1|1,val); 56 else if (r<=mid) add(L,mid,l,r,cur<<1,val); 57 else add(L,mid,l,mid,cur<<1,val),add(mid+1,R,mid+1,r,cur<<1|1,val); 58 } 59 60 int ask(int l,int r,int x,int cur) 61 { 62 push_down(cur,l,r); 63 if (l==r) return num[cur]; 64 int mid=l+r>>1; 65 if (x<=mid) return ask(l,mid,x,cur<<1); 66 else return ask(mid+1,r,x,cur<<1|1); 67 } 68 69 int main() 70 { 71 char ch[9]; 72 for (int i=0;i<=n*4;i++) lazy[i]=-1; 73 while (scanf("%s",ch)!=EOF) 74 { 75 int a=read(),b=read(); 76 if (ch[0]=='U') add(1,n,a,b,1,1); 77 if (ch[0]=='I') add(1,n,1,a-1,1,0),add(1,n,b+1,n,1,0); 78 if (ch[0]=='D') add(1,n,a,b,1,0); 79 if (ch[0]=='C') add(1,n,1,a-1,1,0),add(1,n,a,b,1,2),add(1,n,b+1,n,1,0); 80 if (ch[0]=='S') add(1,n,a,b,1,2); 81 } 82 int h=0,t=0,flag=0; 83 for (int i=1;i<=n;i++) 84 if (ask(1,n,i,1)) 85 { 86 if (!h) h=i; 87 t=i; 88 } 89 else 90 { 91 if (h) 92 { 93 if (flag) printf(" "); 94 else flag=1; 95 if (h&1) printf("("); 96 else printf("["); 97 printf("%d,%d",h/2-1,(t+1)/2-1); 98 if (t&1) printf(")"); 99 else printf("]"); 100 } 101 h=t=0; 102 } 103 if (!flag) printf("empty set"); 104 else printf(" "); 105 return 0; 106 }
转载于:https://www.cnblogs.com/HHshy/p/5734010.html
相关资源：JAVA上百实例源码以及开源项目