題目描述：
定義區間的交，并，差操作。假設當前坐標軸區間集合為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
西月弦 閱讀(1639)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目