poj 3225 区间(区间的交并补操作) - c++编程基础

TOP

poj 3225 区间(区间的交并补操作)

2015-07-20 17:53:04 来源: 作者: 【大中小】浏览:2次

Tags：poj 3225 区间操作

一道题又做了一天。。这道题对我来说起初有N多难点。

1：区间的开闭如何解决。、

2：怎样把区间的交并补、对称差转化为对线段树的操作。

后来与实验室的同学讨论了后解决了前面两个问题。

对于区间的开闭，可以将区间放大一倍，偶数点表示端点，奇数点表示区间内线段，前开的话左端点加1，右开的话右端点减1。例如[1,3]可以表示成[2,6]，(1,3)表示成(3,5)。

对于区间的交并补问题，可以转化为区间覆盖问题，若T区间为[a,b]。

U T:[a,b]覆盖为1.

I T:[0,a-1] [b+1,maxn] 覆盖为0

D T:[a,b]覆盖为0

C T:[0,a-1] [b+1,maxn] 覆盖为0,[a,b]取反

S T:[a,b]取反

然后处理区间的覆盖和异或操作。

起初对异或操作没想到lazy,考虑到异或的性质，两次异或相当于没变。所以节点附加两个信息：col,rev。

col表示覆盖信息，col=0说明全被覆盖为0，col=1说明全被覆盖为1，col=-1说明没有全被覆盖。

rev表示异或信息，rev=1说明区间整体异或，rev=0说明不用异或。

可见只有当col=-1时rev才有用。更新时，若是区间覆盖，相应区间覆盖后抹去异或操作，若是异或操作，判断区间是否完全覆盖，若是直接异或，否则rev进行异或。push_down的时候，若区间完全覆盖，将覆盖信息推送下去并将左右儿子的异或操作抹去，若区间没有完全覆盖，必定有异或操作，将左右儿子可以异或的异或掉，不能异或的将其rev异或。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL long long #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 131072; struct node { int l,r; int col; int rev; }tree[maxn*4]; char s1[10],s2[10]; int a[maxn+10]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].col = 0; tree[v].rev = 0; if(l == r) return; int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); } void push_down(int v) { if(tree[v].l == tree[v].r) return; if(tree[v].col != -1) //区间被完全覆盖 { tree[v*2].col = tree[v*2+1].col = tree[v].col; //向下推送，并把自己的col置为-1 tree[v].col = -1; tree[v].rev = 0; tree[v*2].rev = tree[v*2+1].rev = 0; //儿子节点也被完全覆盖，因此抹去异或操作 } if(tree[v].rev) //区间没被完全覆盖且需要异或 { if(tree[v*2].col != -1) //儿子节点被完全覆盖，直接异或 tree[v*2].col ^= 1; else tree[v*2].rev ^= 1;//否则rev进行异或。 if(tree[v*2+1].col != -1) tree[v*2+1].col ^= 1; else tree[v*2+1].rev ^= 1; tree[v].rev = 0; } } void update(int v, int l, int r, int col) { if(l > r) //l > r的区间忽略不计 return; if(tree[v].l == l && tree[v].r == r) { if(col == 0 || col == 1) { tree[v].col = col; tree[v].rev = 0; } else { if(tree[v].col != -1) tree[v].col ^= 1; else tree[v].rev ^= 1; } return; } push_down(v); int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update(v*2,l,r,col); else if(l > mid) update(v*2+1,l,r,col); else { update(v*2,l,mid,col); update(v*2+1,mid+1,r,col); } } void query(int v) { if(tree[v].col == 1) { for(int i = tree[v].l; i <= tree[v].r; i++) a[i] = tree[v].col; return; } if(tree[v].col == 0) return; if(tree[v].l == tree[v].r) return; push_down(v); query(v*2); query(v*2+1); } int main() { build(1,0,maxn); int l,r,len; memset(a,0,sizeof(a)); while(~scanf(%s %s,s1,s2)) { l = 0; r = 0; len = strlen(s2); int i; for(i = 1; s2[i] >= '0' && s2[i] <= '9'; i++) l = l*10 + s2[i]-'0'; i++; for(; s2[i] >= '0' && s2[i] <= '9'; i++) r = r*10 + s2[i]-'0'; if(s2[0] == '[') l = l*2; else l = l*2+1; if(s2[len-1] == ']') r = r*2; else r = r*2-1; if(s1[0] == 'U') { update(1,l,r,1); } else if(s1[0] == 'I') { update(1,0,l-1,0); update(1,r+1,maxn,0); } else if(s1[0] == 'D') { update(1,l,r,0); } else if(s1[0] == 'C') { update(1,0,l-1,0); update(1,r+1,maxn,0); update(1,l,r,2); //取反 } else { update(1,l,r,2);//取反 } } query(1); int flag = 0; for(int i = 0; i < maxn; i++) { if(a[i] == 1 && (i == 0 || a[i-1] == 0)) l = i; if(a[i] == 1 && (i == maxn-1 || a[i+1] == 0)) { if(flag == 0) flag = 1; else printf( ); if(l%2) printf((); else printf([); printf(%d,,l/2); printf(%d,(i+1)/2); if(i%2) printf()); else printf(]); } } if(flag == 0) printf(empty set ); else printf( ); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：杭电 2602 Bone Collector（背包..	下一篇：UVaOJ-11624-Fire! 解题报告

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: