算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    定义区间的交,并,差操作。假设当前坐标轴区间集合为S(开始为空),给大量的询问,格式为 命令+区间T,命令'I'代表S = S交T,'U'代表并,D和C代表S=S-T和S=T-S,S代表S=S-T并T-S。输出最后的区间集合S。

吐槽:

    1. 从昨天下午做到今天晚上... 好吧我承认我弱
    2. 一开始没有用延时操作,记录了每个操作的时间,最后离线处理。然后我抓狂了....
    3. 后来改用朴素版线段树,写着写着发现这些不是用zkw版线段树也能实现么... 然后就调到了今天晚上...
    4. 由于实现的关系,运行速度与朴素版旗鼓相当..........

算法描述:

    首先将L和R乘以2以解决开闭区间的问题....
    
    剩下的其实就是线段覆盖问题:
        1. U: 将[L,R]赋值为1
        2. I: 将[0,L-1] 和 [R+1,MAXN]赋值为0
        3. D: 将[L,R]赋值为0
        4. S: 将[L,R]里的所有值取反
        5. C: 将[L,R]里的所有值取反,并且将[0,L-1]和[R+1,MAXN]赋值为0
    赋值那部分就不讲了.... 主要是取反,用到线段树的延时操作,然后再下次访问的时候向下更新(朴素版的思路)
    其实zkw版可以先预处理一下,就是将1到L-1的点顺次更新一遍(因为在上面的操作肯定是后加的),然后将1到R+1的点顺次更新一遍。
    这样做一定可以将需要维护的节点预先更新一遍...
    
    最后统计的时候扫一遍就可以了...
    ms比朴素版还是好写一些的...
 1 #include<iostream>
 2 #include<cassert>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 #define re(i,n) for(int i=0;i<n;i++)
 7 #define re1(i,n) for(int i=1;i<=n;i++)
 8 #define re2(i,n) for(int i=0;i<=n;i++)
 9 #define re3(i,n) for(int i=1;i<n;i++)
10 #define debug1
11 const int V = 66000*2;
12 int M;
13 struct node{
14     int color,x;
15     node(){color=x=0;}
16 } seg[V*4];
17 void solve(int x){
18     if(seg[x].color!=-1) seg[x].color ^= 1;
19     else seg[x].x ^= 1;
20 }
21 void upt(int x){
22     if(x==1) return;
23     upt(x>>1);
24     if(x >M) return;
25     if(seg[x].color!=-1){
26         seg[x<<1].color = seg[x<<1|1].color = seg[x].color;
27         seg[x<<1].x = seg[x<<1|1].x =0;
28         seg[x].color = -1;
29     }
30     if(seg[x].x){
31         solve(x <<1);
32         solve(x <<1|1);
33         seg[x].x = 0;
34     }
35 }
36 void ins(int l,int r,int p,int c=0){
37     if(l>r) return;
38     l = M+l; r = M+r+2;
39     upt(l); upt(r);
40     for(;l^r^1;l>>=1,r>>=1){
41         if(l&1^1) if(p) solve(l^1); else seg[l^1].color = c, seg[l^1].x = 0;
42         if(r&1) if(p) solve(r^1); else seg[r^1].color = c, seg[r^1].x = 0;
43     }
44 }
45 inline void OP(int l,int r){
46     printf("%c%d,%d%c ", l&1 ? '(':'[', l>>1 , r&1 ? r+1>>1: r>>1, r&1?')':']');
47 }
48 int main(){
49     char cmd[2];
50     int l,r;char x,y;
51     re(i,30) if((1<<i) > V) {M = 1<<i; break;}
52     while(~scanf("%s %c%d,%d%c",cmd,&x,&l,&r,&y)){
53     //    printf("%s %s\n",cmd,ch);
54         l<<=1,r<<=1; if(x=='(') l++; if(y==')') r--;
55         switch(cmd[0]){
56             case 'U': 
57                 ins(l,r,0,1); break;
58             case 'I': 
59                 ins(0,l-1,0,0); ins(r+1,V,0,0); break;
60             case 'C': 
61                 ins(l,r,1); ins(0,l-1,0,0); ins(r+1,V,0,0); break;
62             case 'D': ins(l,r,0,0); break;
63             case 'S': ins(l,r,1); break;
64         }
65     }
66     int flag = 0,f = 0;
67     for(int i = M+1;i<M+V;i++){
68         upt(i);
69         if(seg[i].color){
70             if(flag) ++r;
71             else r=l=i,flag=1;
72         }
73         else if(flag){
74             f = 1;
75             OP(l-M-1,r-M-1);
76             flag = 0;
77         }
78     }
79     if(!f) puts("empty set"); else
80     puts("");
81 }
82 
posted on 2012-05-07 20:21 西月弦 阅读(1625) 评论(0)  编辑 收藏 引用 所属分类: 解题报告经典题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理