首页 > 代码库 > poj 3225 Help with Intervals
poj 3225 Help with Intervals
http://poj.org/problem?id=3225
题意：对集合进行交、并、差、异或四种操作，输出几步操作的之后的集合。
U [a,b] :可以将[a,b]全部置为1； I [a,b] :可以将[a,b]之外的全部置为0； S-[a,b] :将[a,b]全部置为0； [a,b]-s :将[a,b]之外的全部置为0，[a,b]取反。 I [a,b] :将[a,b]取反。
然后用线段树维护区间。
1 #include <cstdio> 2 #include <cstring> 3 #include<cctype> 4 #include <algorithm> 5 #define maxn 132000 6 using namespace std; 7 const int N=6000000; 8 9 char str[100]; 10 bool visi[N]; 11 struct node 12 { 13 int l,r; 14 int x; 15 bool flag; 16 }tree[N]; 17 18 void build(int i,int l,int r) 19 { 20 tree[i].l=l; 21 tree[i].r=r; 22 tree[i].x=0; 23 tree[i].flag=false; 24 if(l==r) return ; 25 int mid=(l+r)>>1; 26 build(i<<1,l,mid); 27 build(i<<1|1,mid+1,r); 28 } 29 void down(int i) 30 { 31 if(tree[i].l==tree[i].r) 32 { 33 if(tree[i].flag) 34 { 35 tree[i].x^=1; 36 tree[i].flag=false; 37 } 38 return ; 39 } 40 if(tree[i].x!=-1) 41 { 42 if(tree[i].flag) 43 tree[i].x^=1; 44 tree[i<<1].x=tree[i<<1|1].x=tree[i].x; 45 tree[i].x=-1; 46 tree[i<<1].flag=tree[i<<1|1].flag=false; 47 tree[i].flag=false; 48 } 49 if(tree[i].flag) 50 { 51 tree[i].flag=false; 52 if(tree[i<<1].x!=-1) 53 tree[i<<1].x^=1; 54 else 55 tree[i<<1].flag^=true; 56 if(tree[i<<1|1].x!=-1) 57 tree[i<<1|1].x^=1; 58 else 59 tree[i<<1|1].flag^=true; 60 } 61 } 62 void deal(int i,int l,int r,int c) 63 { 64 if(l>r) return; 65 if(tree[i].l==l&&tree[i].r==r) 66 { 67 if(c==0||c==1) 68 { 69 tree[i].x=c; 70 tree[i].flag=false; 71 } 72 else if(tree[i].x!=-1) 73 { 74 tree[i].x^=1; 75 } 76 else 77 tree[i].flag^=1; 78 return ; 79 } 80 down(i); 81 int mid=(tree[i].l+tree[i].r)>>1; 82 if(r<=mid) 83 { 84 deal(i<<1,l,r,c); 85 } 86 else if(l>mid) 87 { 88 deal(i<<1|1,l,r,c); 89 } 90 else 91 { 92 deal(i<<1,l,mid,c); 93 deal(i<<1|1,mid+1,r,c); 94 } 95 } 96 97 void search1(int i) 98 { 99 if(tree[i].x!=-1)100 {101 if(tree[i].x==1)102 {103 for(int j=tree[i].l; j<=tree[i].r; j++)104 visi[j]=true;105 }106 return ;107 }108 down(i);109 search1(i<<1);110 search1(i<<1|1);111 }112 int main()113 {114 build(1,0,maxn);115 while(gets(str))116 {117 int k=strlen(str);118 int x=0,y=0;119 int i;120 for(i=3; i<k; i++)121 {122 if(!isdigit(str[i])) break;123 x=x*10+(str[i]-‘0‘);124 }125 int j;126 for(j=i+1; j<k; j++)127 {128 if(!isdigit(str[j])) break;129 y=y*10+(str[j]-‘0‘);130 }131 if(str[2]==‘[‘) x=x*2;132 else x=x*2+1;133 if(str[j]==‘]‘) y=y*2;134 else y=y*2-1;135 if(str[0]==‘U‘)136 {137 deal(1,x,y,1);138 }139 else if(str[0]==‘I‘)140 {141 deal(1,0,x-1,0);142 deal(1,y+1,maxn,0);143 }144 else if(str[0]==‘D‘)145 {146 deal(1,x,y,0);147 }148 else if(str[0]==‘C‘)149 {150 deal(1,0,x-1,0);151 deal(1,y+1,maxn,0);152 deal(1,x,y,2);153 }154 else if(str[0]==‘S‘)155 {156 deal(1,x,y,2);157 }158 }159 memset(visi,false,sizeof(visi));160 search1(1);161 bool flag=false;162 for(int i=0; i<=maxn; i++)163 {164 if(!visi[i]) continue;165 int xx=i;166 while(visi[i]&&i<=maxn) i++;167 int yy=(--i);168 if(!flag) flag=true;169 else printf(" ");170 if(xx%2==0) printf("[%d,",xx/2);171 else printf("(%d,",xx/2);172 if(yy%2==0) printf("%d]",yy/2);173 else printf("%d)",(yy+1)/2);174 }175 if(!flag) printf("empty set");176 printf("\n");177 return 0;178 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。