poj 3225 Help with Intervals

  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
";

162     return 0;

163 }