题目链接
segment tree
题意
给定集合S，S最初是空集。现对其进行一些操作：与一个集合求交、并、补、对称差。用区间表示出最终的S
分析
这个题有许多注意的地方（当然可能是我写法不太好），肝了一上午……
那么首先想到用线段树来解决这个区间覆盖的问题。虽然是实数区间，但注意到区间端点始终是整数。于是我们整体乘2，用偶数来代表整数点，用奇数来代表两整数之间的开区间。比如2就对应[1,1]，3就对应(1,2)。这样处理起来就十分方便
注意的地方，首先小心空集，比如(1,1)，[1,1)，(1,1]这样的区间，不处理的话会RE。然后注意线段树区间修改中lazy-tag退化的问题，我开始的一种写法PushDown的次数太多了，结果T了，后来直接把翻转记录到lazy-tag中就解决了。
AC代码
//POJ 3225 Help with Intervals
//AC 2016-10-26 11:58:32
//segment tree
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <sstream>
#include <stack>
using namespace std;
#define cls(x) memset(x,0,sizeof x)
#define inf(x) memset(x,0x3f,sizeof x)
#define neg(x) memset(x,-1,sizeof x)
#define ninf(x) memset(x,0xc0,sizeof x)
#define st0(x) memset(x,false,sizeof x)
#define st1(x) memset(x,true,sizeof x)
#define lowbit(x) x&(-x)
#define input(x) scanf("%d",&(x))
#define inputt(x,y) scanf("%d %d",&(x),&(y))
#define bug cout<<"here"<<endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")//stack expansion
//#define debug
const double PI=acos(-1.0);
const int INF=0x3f3f3f3f;//1061109567-2147483647
const long long LINF=0x3f3f3f3f3f3f3f3f;//4557430888798830399-9223372036854775807
const int maxn=70000*2+100;
/* 线段树 */
struct segNode
{
int left,right;//结点对应的区间端点
/*结点的性质*/
int sum;
/*成段更新的记录*/
int lazy;
};
struct segTree
{
segNode tree[maxn*4+10];
int fl,fr,l,r,first;
void invert(int x)
{
if(tree[x].lazy==1)
tree[x].lazy=0;
else if(tree[x].lazy==0)
tree[x].lazy=1;
else if(tree[x].lazy==2)
tree[x].lazy=-1;
else
tree[x].lazy=2;
return;
}
/* 由子结点回溯 */
void Push_Up(int x)
{
tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
return;
}
/* 向下更新 */
void Push_Down(int x)
{
if(tree[x].lazy==2)
{
//tree[x<<1].lazy=tree[x<<1|1].lazy=tree[x].lazy;
invert(x<<1);
invert(x<<1|1);
tree[x<<1].sum=tree[x<<1].right-tree[x<<1].left+1-tree[x<<1].sum;
tree[x<<1|1].sum=tree[x<<1|1].right-tree[x<<1|1].left+1-tree[x<<1|1].sum;
tree[x].lazy=-1;
}
else if(tree[x].lazy!=-1)
{
tree[x<<1].lazy=tree[x<<1|1].lazy=tree[x].lazy;
tree[x<<1].sum=tree[x].lazy*(tree[x<<1].right-tree[x<<1].left+1);
tree[x<<1|1].sum=tree[x].lazy*(tree[x<<1|1].right-tree[x<<1|1].left+1);
tree[x].lazy=-1;
}
return;
}
/* 线段树构造函数 */
void build(int x,int left,int right)
{
tree[x].left=left;
tree[x].right=right;
tree[x].sum=0;
tree[x].lazy=0;
if(left==right)//只有一个元素时
return;
/*递归构造子树*/
int mid=(left+right)>>1;
build(x<<1,left,mid);
build(x<<1|1,mid+1,right);
/* 回溯构造 */
Push_Up(x);
return;
}
/* 成段更新 */
void update(int x,int start,int endd,int v)
{
if(start==tree[x].left&&endd==tree[x].right)//整段直接更新
{
tree[x].lazy=v;
tree[x].sum=(tree[x].right-tree[x].left+1)*v;
return;
}
Push_Down(x);//需要子节点的真实信息
int mid=(tree[x].left+tree[x].right)>>1;
if(endd<=mid)//更新区间完全在左子结点中
update(x<<1,start,endd,v);
else if(start>mid)//更新区间完全在右子结点中
update(x<<1|1,start,endd,v);
else
{
update(x<<1,start,mid,v);
update(x<<1|1,mid+1,endd,v);
}
Push_Up(x);//回溯更新
}
void updateI(int x,int start,int endd)
{
if(start==tree[x].left&&endd==tree[x].right)
return;
Push_Down(x);
int mid=(tree[x].left+tree[x].right)>>1;
if(endd<=mid)//更新区间完全在左子结点中
{
updateI(x<<1,start,endd);
update(x<<1|1,tree[x<<1|1].left,tree[x<<1|1].right,0);
}
else if(start>mid)//更新区间完全在右子结点中
{
updateI(x<<1|1,start,endd);
update(x<<1,tree[x<<1].left,tree[x<<1].right,0);
}
else
{
updateI(x<<1,start,mid);
updateI(x<<1|1,mid+1,endd);
}
Push_Up(x);//回溯更新
}
void updateC(int x,int start,int endd)
{
if(start==tree[x].left&&endd==tree[x].right)
{
tree[x].sum=tree[x].right-tree[x].left+1-tree[x].sum;
invert(x);
return;
}
Push_Down(x);
int mid=(tree[x].left+tree[x].right)>>1;
if(endd<=mid)//更新区间完全在左子结点中
{
updateC(x<<1,start,endd);
update(x<<1|1,tree[x<<1|1].left,tree[x<<1|1].right,0);
}
else if(start>mid)//更新区间完全在右子结点中
{
updateC(x<<1|1,start,endd);
update(x<<1,tree[x<<1].left,tree[x<<1].right,0);
}
else
{
updateC(x<<1,start,mid);
updateC(x<<1|1,mid+1,endd);
}
Push_Up(x);//回溯更新
}
void updateS(int x,int start,int endd)
{
if(start==tree[x].left&&endd==tree[x].right)
{
tree[x].sum=tree[x].right-tree[x].left+1-tree[x].sum;
invert(x);
return;
}
Push_Down(x);
int mid=(tree[x].left+tree[x].right)>>1;
if(endd<=mid)//更新区间完全在左子结点中
updateS(x<<1,start,endd);
else if(start>mid)//更新区间完全在右子结点中
updateS(x<<1|1,start,endd);
else
{
updateS(x<<1,start,mid);
updateS(x<<1|1,mid+1,endd);
}
Push_Up(x);//回溯更新
}
void print(int a,int b)
{
if(first)
first=0;
else
putchar(' ');
if(a&1)
printf("(%d,",a/2);
else
printf("[%d,",a/2);
if(b&1)
printf("%d)",b/2+1);
else
printf("%d]",b/2);
return;
}
void dfs(int x)
{
if(tree[x].sum==tree[x].right-tree[x].left+1)
{
l=tree[x].left;
r=tree[x].right;
if(l==fr+1)
fr=r;
else
{
if(fr!=-10)
print(fl,fr);
fl=l;fr=r;
}
return;
}
if(tree[x].right!=tree[x].left)
{
Push_Down(x);
dfs(x<<1);
dfs(x<<1|1);
}
return;
}
void answer()
{
fl=fr=-10;
first=1;
if(tree[1].sum==0)
{
printf("empty set
");
return;
}
dfs(1);
print(fl,fr);
putchar('
');
return;
}
}setT;
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
#ifdef debug
freopen("E:\Documents\code\input.txt","r",stdin);
freopen("E:\Documents\code\output.txt","w",stdout);
#endif
//IO
char opr[5],inter[50];
setT.build(1,0,70000*2);
while(scanf("%s",opr)!=EOF)
{
int lc,rc;
int l,r;
getchar();
if(getchar()=='[')
lc=1;
else
lc=0;
scanf("%d,%d",&l,&r);
l*=2;
r*=2;
if(getchar()==']')
rc=1;
else
rc=0;
getchar();
if((!rc||!lc)&&l==r)
{
if(opr[0]=='I'||opr[0]=='C')
setT.update(1,0,132000,0);
continue;
}
if(!lc) ++l;
if(!rc) --r;
if(opr[0]=='U')
setT.update(1,l,r,1);
if(opr[0]=='I')
setT.updateI(1,l,r);
if(opr[0]=='D')
setT.update(1,l,r,0);
if(opr[0]=='C')
setT.updateC(1,l,r);
if(opr[0]=='S')
setT.updateS(1,l,r);
}
setT.answer();
return 0;
}