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

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

代码:

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<map>

 #include<cctype>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 const int inf=0x3f3f3f3f;

 const double eps=1e-;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 int col[maxn<<],Xor[maxn<<],hash[maxn<<];

 void fxor(int rt)

 {

     if(col[rt]!=-)col[rt]^=;

     else Xor[rt]^=;

 }

 void pushdown(int rt)

 {

     if(col[rt]!=-){

         col[rt<<]=col[rt<<|]=col[rt];

         Xor[rt<<]=Xor[rt<<|]=;

         col[rt]=-;

     }

     if(Xor[rt]){

         fxor(rt<<);

         fxor(rt<<|);

         Xor[rt]=;

     }

 }

 void update(char op,int L,int R,int l,int r,int rt)

 {

     if(L<=l&&r<=R){

         if(op=='U'){

             col[rt]=;

             Xor[rt]=;

         }

         else if(op=='D'){

             col[rt]=;

             Xor[rt]=;

         }

         else if(op=='C'||op=='S'){

             fxor(rt);

         }

         return ;

     }

     pushdown(rt);

     int m=(l+r)>>;

     if(L<=m)update(op,L,R,lson);

     else if(op=='I'||op=='C'){

         Xor[rt<<]=col[rt<<]=;

     }

     if(R> m)update(op,L,R,rson);

     else if(op=='I'||op=='C'){

         Xor[rt<<|]=col[rt<<|]=;

     }

 }

 void query(int l,int r,int rt)

 {

     if(col[rt]==){

         for(int i=l;i<=r;i++){

             hash[i]=;

         }

         return ;

     }

     else if(col[rt]==)return ;

     if(l==r) return ;

     pushdown(rt);

     int m=(l+r)>>;

     query(lson);

     query(rson);

 }

 int main()

 {

     col[]=Xor[]=;

     char op,l,r;

     int a,b;

     while(~scanf("%c %c%d,%d%c\n",&op,&l,&a,&b,&r)){

         a<<=,b<<=;

         if(l=='(')a++;

         if(r==')')b--;

         if(a>b){

             if(op=='C'||op=='I'){

                 col[]=Xor[]=;

             }

         }

         else

             update(op,a,b,,maxn,);

     }

     query(,maxn,);

     int flag=;

     int s=-,e;

     for(int i=;i<=maxn;i++){

         if(hash[i]){

             if(s==-)s=i;

             e=i;

         }

         else{

             if(s!=-){

                 if(flag)printf(" ");

                 flag=;

                 printf("%c%d,%d%c",s&?'(':'[',s>>,(e+)>>,e&?')':']');

                 s=-;

             }

         }

     }

     if(!flag)printf("empty set");

     puts("");

     return ;

 }

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

滚了滚了。。。

巴特西

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

最新文章

热门文章