POJ3225Help with Intervals - c++编程基础

TOP

POJ3225Help with Intervals

2015-07-20 17:49:35 来源: 作者: 【大中小】浏览:1次

开始没看懂题，看懂了之后也不知道如何用线段树来做这题，百度了一下思路

思路:
我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含)
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换

还有要注意的地方是把数组开为2倍，才可以用节点表示区间；注意a为0时的情况

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; #define INF 0xfffffff #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 132000 int col[maxn<<2]; void pushdown(int rt) { if(col[rt]==2) { col[rt<<1]=1-col[rt<<1]; col[rt<<1|1]=1-col[rt<<1|1]; col[rt]=-1; } if(col[rt]!=-1) { col[rt<<1]=col[rt<<1|1]=col[rt]; col[rt]=-1; } } void update(int L,int R,int add,int l,int r,int rt) { if(L<=l&&R>=r) { if(add==2) col[rt]=1-col[rt]; else col[rt]=add; return ; } pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,add,lson); if(R>m) update(L,R,add,rson); } int query(int key,int l,int r,int rt) { if(l==r) return col[rt]; pushdown(rt); int m=(l+r)>>1; if(key<=m) query(key,lson); else query(key,rson); } int main() { char operation,bracket1,bracket2,nullity; int a,b; memset(col,0,sizeof(col)); while(scanf(" %c %c%d %c%d %c",&operation,&bracket1,&a,&nullity,&b,&bracket2)!=-1) { a=a<<1; b=b<<1; if(bracket1=='(') a++; if(bracket2==')') b--; if(operation=='U') { update(a,b,1,0,maxn,1); } else if(operation=='I') { if(a<=0) a=1; update(0,a-1,0,0,maxn,1); update(b+1,maxn,0,0,maxn,1); } else if(operation=='D') { update(a,b,0,0,maxn,1); } else if(operation=='C') { update(a,b,2,0,maxn,1); if(a<=0) a=1; update(0,a-1,0,0,maxn,1); update(b+1,maxn,0,0,maxn,1); } else if(operation=='S') { update(a,b,2,0,maxn,1); } } int flag=1,num=0; for(int i=0;i
               
                >1); else printf("[%d,",i>>1); } if(!flag&&!k) { flag=1; i--; if(i&1) printf("%d) ",(i+1)>>1); else printf("%d] ",(i+1)>>1); } } if(!num) printf("empty set\n"); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：CodeForces 34D Road Map	下一篇：杭电 2176 取(m堆)石子游戏（博弈..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: