POJ 3225.Help with Intervals-线段树(成段替换、区间异或、简单hash)

这个题就是对区间的各种操作，感觉这道题写的一点意思都没有，写到后面都不想写了，而且更神奇的是，自己的编译器连结果都输不出来，但是交上就过了，也是令人头大的操作，这题没意思，不要写了。我写到后面就写不下去了，直接去看了别人的代码。。。

代码:

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<cstdlib>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<stack>
  9 #include<map>
 10 #include<cctype>
 11 using namespace std;
 12 typedef long long ll;
 13 const int maxn=131072;
 14 const int inf=0x3f3f3f3f;
 15 const double eps=1e-5;
 16 #define lson l,m,rt<<1
 17 #define rson m+1,r,rt<<1|1
 18 
 19 int col[maxn<<2],Xor[maxn<<2],hash[maxn<<2];
 20 
 21 void fxor(int rt)
 22 {
 23     if(col[rt]!=-1)col[rt]^=1;
 24     else Xor[rt]^=1;
 25 }
 26 void pushdown(int rt)
 27 {
 28     if(col[rt]!=-1){
 29         col[rt<<1]=col[rt<<1|1]=col[rt];
 30         Xor[rt<<1]=Xor[rt<<1|1]=0;
 31         col[rt]=-1;
 32     }
 33     if(Xor[rt]){
 34         fxor(rt<<1);
 35         fxor(rt<<1|1);
 36         Xor[rt]=0;
 37     }
 38 }
 39 void update(char op,int L,int R,int l,int r,int rt)
 40 {
 41     if(L<=l&&r<=R){
 42         if(op=='U'){
 43             col[rt]=1;
 44             Xor[rt]=0;
 45         }
 46         else if(op=='D'){
 47             col[rt]=0;
 48             Xor[rt]=0;
 49         }
 50         else if(op=='C'||op=='S'){
 51             fxor(rt);
 52         }
 53         return ;
 54     }
 55 
 56     pushdown(rt);
 57     int m=(l+r)>>1;
 58     if(L<=m)update(op,L,R,lson);
 59     else if(op=='I'||op=='C'){
 60         Xor[rt<<1]=col[rt<<1]=0;
 61     }
 62     if(R> m)update(op,L,R,rson);
 63     else if(op=='I'||op=='C'){
 64         Xor[rt<<1|1]=col[rt<<1|1]=0;
 65     }
 66 }
 67 void query(int l,int r,int rt)
 68 {
 69     if(col[rt]==1){
 70         for(int i=l;i<=r;i++){
 71             hash[i]=1;
 72         }
 73         return ;
 74     }
 75     else if(col[rt]==0)return ;
 76     if(l==r) return ;
 77 
 78     pushdown(rt);
 79     int m=(l+r)>>1;
 80     query(lson);
 81     query(rson);
 82 }
 83 int main()
 84 {
 85     col[1]=Xor[1]=0;
 86     char op,l,r;
 87     int a,b;
 88     while(~scanf("%c %c%d,%d%c
",&op,&l,&a,&b,&r)){
 89         a<<=1,b<<=1;
 90         if(l=='(')a++;
 91         if(r==')')b--;
 92         if(a>b){
 93             if(op=='C'||op=='I'){
 94                 col[1]=Xor[1]=0;
 95             }
 96         }
 97         else
 98             update(op,a,b,0,maxn,1);
 99     }
100     query(0,maxn,1);
101     int flag=0;
102     int s=-1,e;
103     for(int i=0;i<=maxn;i++){
104         if(hash[i]){
105             if(s==-1)s=i;
106             e=i;
107         }
108         else{
109             if(s!=-1){
110                 if(flag)printf(" ");
111                 flag=1;
112                 printf("%c%d,%d%c",s&1?'(':'[',s>>1,(e+1)>>1,e&1?')':']');
113                 s=-1;
114             }
115         }
116     }
117     if(!flag)printf("empty set");
118     puts("");
119     return 0;
120 }

5道题解完成，感觉后面再写题就应该是要用脑子来写了，水题水一下就可以了，就这样吧，下次再集齐5道再来写线段树可真有意思呢续集(3)。

滚了滚了。。。