题目描述：
定义区间的交，并，差操作。假设当前坐标轴区间集合为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
西月弦 阅读(1629)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目