【POJ】3225 Help with Intervals

  1 #include<cstdio>
  2 #include<cstring>
  3 #define MAXN 131080
  4 #define INF 987654321
  5 int lazy[MAXN<<2],cover[MAXN<<2];
  6 bool vis[MAXN<<1];
  7 inline void FXOR(int rt)
  8 {
  9     if(cover[rt]!=-1)
 10     {
 11         cover[rt]^=1;
 12         lazy[rt]=0;
 13     }
 14     else
 15         lazy[rt]^=1;
 16 }
 17 inline void PushDown(int rt)
 18 {
 19     if(cover[rt]!=-1)
 20     {
 21         cover[rt<<1]=cover[rt<<1|1]=cover[rt];
 22         lazy[rt<<1]=lazy[rt<<1|1]=0;
 23         cover[rt]=-1;
 24     }
 25     else if(lazy[rt])
 26     {
 27         FXOR(rt<<1);
 28         FXOR(rt<<1|1);
 29         lazy[rt]=0;
 30     }
 31 }
 32 void Change(int x,int y,int L,int R,int rt)
 33 {
 34     if(x<=L&&R<=y)
 35         FXOR(rt);
 36     else
 37     {
 38         int mid=(L+R)>>1;
 39         PushDown(rt);
 40         if(mid>=x)
 41             Change(x,y,L,mid,rt<<1);
 42         if(y>mid)
 43             Change(x,y,mid+1,R,rt<<1|1);
 44     }
 45 }
 46 void Update(int x,int y,int val,int L,int R,int rt)
 47 {
 48     if(x<=L&&R<=y)
 49     {
 50         lazy[rt]=0;
 51         cover[rt]=val;
 52     }
 53     else
 54     {
 55         int mid=(L+R)>>1;
 56         PushDown(rt);
 57         if(mid>=x)
 58             Update(x,y,val,L,mid,rt<<1);
 59         if(y>mid)
 60             Update(x,y,val,mid+1,R,rt<<1|1);
 61     }
 62 }
 63 void Query(int L,int R,int rt)
 64 {
 65     if(cover[rt]==1)
 66     {
 67         for(int i=L;i<=R;i++)
 68             vis[i]=true;
 69     }
 70     else if(cover[rt]==-1&&L!=R)
 71     {
 72         int mid=(L+R)>>1;
 73         PushDown(rt);
 74         Query(L,mid,rt<<1);
 75         Query(mid+1,R,rt<<1|1);
 76     }
 77 }
 78 int main()
 79 {
 80     char ch,left,right;
 81     int x,y,i,j;
 82     bool flag;
 83     memset(cover,0,sizeof(cover));
 84     memset(lazy,0,sizeof(lazy));
 85     while(~scanf(" %c %c%d,%d %c",&ch,&left,&x,&y,&right))
 86     {
 87         x<<=1;
 88         y<<=1;
 89         if(left=='(')
 90             x++;
 91         if(right==')')
 92             y--;
 93         if(x>y)
 94             continue;
 95         if(ch=='U')
 96             Update(x,y,1,0,MAXN,1);
 97         else if(ch=='I')
 98         {
 99             if(x>0)
100                 Update(0,x-1,0,0,MAXN,1);
101             if(y<MAXN)
102                 Update(y+1,MAXN,0,0,MAXN,1);
103         }
104         else if(ch=='D')
105             Update(x,y,0,0,MAXN,1);
106         else if(ch=='C')
107         {
108             if(x>0)
109                 Update(0,x-1,0,0,MAXN,1);
110             if(y<MAXN)
111                 Update(y+1,MAXN,0,0,MAXN,1);
112             Change(x,y,0,MAXN,1);
113         }
114         else
115             Change(x,y,0,MAXN,1);
116     }
117     memset(vis,false,sizeof(vis));
118     Query(0,MAXN,1);
119     flag=false;
120     for(i=0;i<=MAXN;i++)
121     {
122         if(vis[i])
123         {
124             for(j=i;j<=MAXN&&vis[j];j++);
125             x=i;
126             y=j-1;
127             if(flag)
128                 putchar(' ');
129             printf("%c%d,%d%c",x&1?'(':'[',x>>1,(y+1)>>1,y&1?')':']');
130             flag=true;
131             i=j;
132         }
133     }
134     if(flag)
135         putchar('\n');
136     else
137         puts("empty set");
138     return 0;
139 }
新博客：www.zhixiangli.com