poj3225Help with Intervals（线段树求区间交并补）

先贴代码有空再解释
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define N 140000
  7 int s[N<<2],kc[N<<2],hash[N];
  8 void build(int l,int r,int w)
  9 {
 10     kc[w] = 0;
 11     s[w] = 0;
 12     if(l==r)
 13     return ;
 14     int m = (l+r)>>1;
 15     build(l,m,w<<1);
 16     build(m+1,r,w<<1|1);
 17 }
 18 void fxor(int w)
 19 {
 20     if(s[w]!=-1)
 21     s[w]^=1;
 22     else
 23     kc[w]^=1;
 24 }
 25 void pushdown(int w)
 26 {
 27     if(s[w]!=-1)
 28     {
 29         s[w<<1] = s[w<<1|1] = s[w];
 30         kc[w<<1] = kc[w<<1|1]= 0;
 31         s[w] = -1;
 32     }
 33     if(kc[w])
 34     {
 35         fxor(w<<1);
 36         fxor(w<<1|1);
 37         kc[w] = 0;
 38     }
 39 }
 40 void update(int a,int b,char c,int l,int r,int w)
 41 {
 42     int i;
 43     if(a<=l&&b>=r)
 44     {
 45         if(c=='U')
 46         {
 47             s[w] = 1;
 48             kc[w] = 0;
 49         }
 50         else
 51         if(c=='D')
 52         {
 53             s[w] = 0;
 54             kc[w] = 0;
 55         }
 56         else
 57         if(c=='C'||c=='S')
 58         fxor(w);
 59         return ;
 60     }
 61     pushdown(w);
 62     int m = (l+r)>>1;
 63     if(a<=m)
 64     update(a,b,c,l,m,w<<1);
 65     else
 66     {
 67         if(c=='C'||c=='I')
 68         {
 69             s[w<<1] = 0;
 70             kc[w<<1] = 0;
 71         }
 72     }
 73     if(b>m)
 74     update(a,b,c,m+1,r,w<<1|1);
 75     else
 76     {
 77         if(c=='C'||c=='I')
 78         {
 79             s[w<<1|1] = 0;
 80             kc[w<<1|1] = 0;
 81         }
 82     }
 83 }
 84 void query(int l,int r,int w)
 85 {
 86     if(s[w]==1)
 87     {
 88         for(int i = l ; i <= r ; i++)
 89         hash[i] = 1;
 90         return ;
 91     }
 92     else
 93     if(s[w]==0)
 94     return ;
 95     if(l==r)
 96     return ;
 97     pushdown(w);
 98     int m = (l+r)>>1;
 99     query(l,m,w<<1);
100     query(m+1,r,w<<1|1);
101 }
102 int main()
103 {
104     int a,b,i,j,k,n;
105     char c,c1,c2;
106     build(0,N,1);
107     while(scanf("%c %c%d,%d%c%*c",&c,&c1,&a,&b,&c2)!=EOF)
108     {
109                a <<= 1;
110         b <<= 1;
111         if(c1=='(')
112            a++;
113         if(c2==')')
114            b--;
115         if(a>b)
116         {
117             if(c=='C'||c=='I')
118             s[1] = kc[1] = 0;
119         }
120         else
121         update(a,b,c,0,N,1);
122      }
123     query(0,N,1);
124     int f = 0,w = 0,flag = 0;
125     for(i = 0; i <= N ; i++)
126     {
127         if(!f&&hash[i])
128         {
129             if(flag)
130             printf(" ");
131             if(i%2!=0)
132             printf("(");
133             else
134             printf("[");
135             printf("%d,",i/2);
136             f = 1;
137             flag = 1;
138             w = 0;
139         }
140         else
141         if(!hash[i]&&!w&&f)
142         {
143             int ii=i;
144             if(ii%2==0)
145             ii++;
146             else
147             ii--;
148             printf("%d",ii/2);
149             if(ii%2!=0)
150             printf(")");
151             else
152             printf("]");
153             f = 0;
154             w = 1;
155         }
156         else
157         if(!hash[i])
158         f = 0;
159     }
160     if(!flag)
161     cout<<"empty set\n";
162     return 0;
163 }