bzoj 3226 [Sdoi2008]校门外的区间（线段树）

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 const int N = 150000+10;
  7 
  8 struct Tree{ int l,r,v,setv,rev; }T[N<<1];
  9 
 10 void build(int u,int L,int R) {
 11     T[u].l=L,T[u].r=R,T[u].setv=-1;T[u].rev=0;
 12     if(L==R) return ;
 13     int M=(L+R)>>1;
 14     build(u<<1,L,M); build(u<<1|1,M+1,R);
 15 }
 16 void pushdown(int u) {
 17     int lc=u<<1,rc=lc|1;
 18     if(T[u].l==T[u].r) {
 19         if(T[u].setv!=-1) T[u].v=T[u].setv;
 20         T[u].v^=T[u].rev; 
 21     }
 22     else {
 23         if(T[u].setv!=-1) {            //AT: set->rev=0 所以rev的执行顺序在set之后 
 24             T[lc].setv=T[rc].setv=T[u].setv;
 25             T[lc].rev=T[rc].rev=0;
 26         }
 27         T[lc].rev^=T[u].rev,T[rc].rev^=T[u].rev;
 28     }
 29     T[u].setv=-1, T[u].rev=0;
 30 }
 31 void update(int u,int L,int R,int x) {
 32     pushdown(u);
 33     if(L<=T[u].l && T[u].r<=R) {
 34         if(x==-1) T[u].rev^=1;
 35         else T[u].setv=x;
 36     }
 37     else {
 38         int M=(T[u].l+T[u].r)>>1;
 39         if(L<=M) update(u<<1,L,R,x);
 40         if(M<R) update(u<<1|1,L,R,x);
 41     }
 42 }
 43 int query(int u,int x) {
 44     pushdown(u);
 45     if(T[u].l==T[u].r) return T[u].v;
 46     else {
 47         int M=(T[u].l+T[u].r)>>1;
 48         if(x<=M) return query(u<<1,x);
 49         else return query(u<<1|1,x);
 50     }
 51 }
 52 void reverse(int u,int L,int R) { update(u,L,R,-1); }
 53 
 54 char s[2];
 55 void read(int& x) {
 56     char c=getchar(); int f=0; x=0;
 57     while(!isdigit(c)) { if(c==‘(‘) f=1; c=getchar(); }
 58     while(isdigit(c))
 59         x=x*10+c-‘0‘ , c=getchar();
 60     if(c==‘)‘) f=-1;
 61     x=x*2+f;
 62 }
 63 int main() {
 64     //freopen("in.in","r",stdin);
 65     //freopen("out.out","w",stdout);
 66     int n=65536*2+1;
 67     build(1,1,n);
 68     while(scanf("%s",s)==1) {
 69         int a,b;
 70         read(a),read(b);
 71         a+=2; b+=2;
 72         switch(s[0]) {
 73             case ‘U‘:
 74                 update(1,a,b,1); break;
 75             case ‘I‘:
 76                 update(1,1,a-1,0),update(1,b+1,n,0); break;
 77             case ‘D‘:
 78                 update(1,a,b,0); break;
 79             case ‘C‘:
 80                 update(1,1,a-1,0),update(1,b+1,n,0);
 81                 reverse(1,a,b); break;
 82             case ‘S‘:
 83                 reverse(1,a,b); break;
 84         }
 85     }
 86     int f=-1,r=-1,flag=0;
 87     for(int i=1;i<=n;i++)
 88     {
 89         if(query(1,i)) { if(f==-1) f=i; r=i; }
 90         else {
 91             if(f!=-1) {
 92                 if(flag) putchar(‘ ‘);
 93                 else flag=1;
 94                 if(f&1) putchar(‘(‘);
 95                 else putchar(‘[‘);
 96                 printf("%d,%d",f/2-1,(r+1)/2-1);
 97                 if(r&1) putchar(‘)‘);
 98                 else putchar(‘]‘);
 99             }
100             f=r=-1;
101         }
102     }
103     if(!flag) puts("empty set");
104     return 0;
105 }