Poj3225Help with Intervals区间线段树-白红宇

Poj3225Help with Intervals区间线段树

阅读量：5063 次

发布时间：2019-06-12

本文共 2498 字，大约阅读时间需要 8 分钟。

　　这题不说了，都是泪。这题拆点。开始很戳的把更新分开成一部分写，然后一直re。。后来学了这种直接在更新里把所有的搞了的搞法，愈发的感觉自己蠢了。

先说下题意：将一个集合经过并交补，然后求最后的集合。

搞法：U [l,r] 将[l,r] 置为1

D [l,r] 将[l,r] 置为0

S [l,r] 将[l,r] 0和1 交换

I [l,r] 将 (-INF,l) 和(r,INF) 清0

C[l,r] 将 [l,r]0 ，1互换并且执行I操作。

一空集 U [1,5] 然后这个集合就成了 [1,5];

（2,3）不是空集，2.50也算。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include
                 
                  #include
                  
                   using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 65545 * 2;int color[maxn << 2], sign[maxn << 2];int Hash[maxn<<2];void gao(int rt){ if (~color[rt]) color[rt] ^= 1; else sign[rt] ^= 1;}void down(int rt){ if (~color[rt]){ color[rt << 1] = color[rt << 1 | 1] = color[rt]; sign[rt << 1] = sign[rt << 1 | 1] = 0; color[rt] = -1; } if (sign[rt]){ gao(rt << 1); gao(rt << 1 | 1); sign[rt] = 0; }}void update(int L, int R, int add, int l, int r, int rt){ if (L <= l&&r <= R){ if (add == 1) color[rt] = 1, sign[rt] = 0; if (add == 0) color[rt] = 0, sign[rt] = 0; if (add == -1) gao(rt); return; } int mid = (l + r) >> 1; down(rt); if (L <= mid) update(L, R, add, lson); if (R > mid) update(L, R, add, rson);}void ask(int l, int r, int rt){ if (color[rt] == 1){ for (int i = l; i <= r; i++) Hash[i] = 1; return; } if(l==r){ if(sign[rt]) Hash[l]=1;return ; } if (color[rt] == 0) return; down(rt); int mid = (l + r) >> 1; ask(lson); ask(rson);}int main(){ char str[100], str1[100]; int a; int b; char c2,c1; memset(Hash, 0, sizeof(Hash)); memset(color,-1,sizeof(color)); while (scanf("%s %c%d,%d%c", str, &c1,&a,&b,&c2) != EOF){ char c = str[0]; a *= 2; b *= 2; if (c1 == '(') a++; if (c2 == ')') b--; if (c == 'U'){ update(a, b, 1, 0, maxn, 1); } if (c == 'D'){ update(a, b, 0, 0, maxn, 1); } if (c == 'S'){ update(a, b, -1, 0, maxn, 1); } if (c == 'I'){ if(a<=0) a=1; if(b+1>maxn) b=maxn-1; update(0, a - 1, 0, 0, maxn, 1); update(b + 1, maxn, 0, 0, maxn, 1); } if (c == 'C'){ if(a<=0) a=1; if(b+1>maxn) b=maxn-1; update(0, a - 1, 0, 0, maxn, 1); update(b + 1, maxn, 0, 0, maxn, 1); update(a, b, -1, 0, maxn, 1); } } ask(0, maxn, 1); bool flag=false; int s=-1,t=-1; for(int i=0;i<=maxn;++i){ if(Hash[i])s=(s==-1?i:s),t=i; else if(s != -1){ if(flag)printf(" "); flag=true; printf("%c%d,%d%c",s&1?'(':'[',s>>1,(t+1)>>1,t&1?')':']'); s=-1; } } if(!flag)printf("empty set"); printf("\n"); return 0;}