本文主要是介绍poj3225 Help with Intervals，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：全集是[0,65535]，初始集合为空集，进行各种集合运算，区间升序输出最后的集合。
思路：线段树（区间更新）。把原来的范围扩大一倍来表示开闭区间应该是很容易想到的。关于集合运算，其实把那5中操作提炼一下，可以变成两种操作，一是区间赋值为1（0），二是区间取反。其中区间取反的更新操作我写退化了一次，然后超时了。。正确的做法是用另一个标记记录这个区间有没有被取反。我的线段树风格可能不是那么好看，只写了更新和查询两个函数。。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define ll long longusing namespace std; struct node{int l; int r;bool val;bool flag;bool inv;
};node tree[540000];void build_tree(int n,int l,int r){tree[n].l=l; tree[n].r=r;tree[n].val=0; tree[n].flag=1; tree[n].inv=0;if(l==r)return;int mid=(l+r)/2;build_tree(n*2,l,mid);build_tree(n*2+1,mid+1,r);
}void update(int n,int l,int r,int type ){if(tree[n].l==l&&tree[n].r==r){if(type==1){tree[n].val=1;tree[n].inv=0;tree[n].flag=1;}if(type==0){tree[n].val=0;tree[n].inv=0;tree[n].flag=1;}if(type==2)tree[n].inv^=1;return;}if(tree[n].l==tree[n].r)return;int mid=(tree[n].l+tree[n].r)/2;if(tree[n].flag){update(n*2,tree[n].l,mid,tree[n].val);update(n*2+1,mid+1,tree[n].r,tree[n].val);tree[n].flag=0;}if(tree[n].inv){tree[n*2].inv^=tree[n].inv;tree[n*2+1].inv^=tree[n].inv; tree[n].inv=0;}if(r<=mid){update(n*2,l,r,type);}else{if(l<=mid){update(n*2,l,mid,type);update(n*2+1,mid+1,r,type);}else{update(n*2+1,l,r,type);}}
}bool query(int n,int pos){if(tree[n].flag){if(tree[n].inv)return !tree[n].val;return tree[n].val;}int mid=(tree[n].l+tree[n].r)/2;if(pos<=mid){return tree[n].inv^query(n*2,pos);}else{return tree[n].inv^query(n*2+1,pos);}
}bool output(){bool s=query(1,0);bool fir=1;if(s){fir=0;printf("[0,");}for(int i=1;i<=132000;i++){if(query(1,i)!=s){if(s){printf("%d",i/2);if(i%2){printf("]");}else{printf(")");}}else{if(!fir)printf(" ");fir=0;if(i%2){printf("(");}else{printf("[");}printf("%d,",i/2);}s=!s;}}if(fir)return 0;printf("\n");return 1;
}int main(){char oper,c;build_tree(1,0,132000);while(~scanf("%c ",&oper)){char lb,rb;int ln,rn;scanf("%c%d%c%d%c%c",&lb,&ln,&c,&rn,&rb,&c);ln=ln*2; if(lb=='(')ln++;rn=rn*2; if(rb==')')rn--;if(ln>rn)continue;if(oper=='U'){update(1,ln,rn,1);}else if(oper=='I'){update(1,0,ln-1,0);update(1,rn+1,132000,0);}else if(oper=='D'){update(1,ln,rn,0);}else if(oper=='C'){update(1,0,ln-1,0);update(1,rn+1,132000,0);update(1,ln,rn,2);}else if(oper=='S'){update(1,ln,rn,2);} }if(!output()){printf("empty set\n");}return 0;
}
这篇关于poj3225 Help with Intervals的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
