http://blog.csdn.net/niuox/article/details/9664487
这道题明显是线段树，根据题意可以知道：
(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含)
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
这里有两个地方和区间更新不一样
一个是会更新选中区间以外的所有区域，可以这样子解决：
void update(char val,int L,int R,int l,int r,int rt)
{
...
int mid = (l + r)>>;
if (L <= mid)
{
update(val,L,R,l,mid,rt<<);
}
else if(val == 'I' || val == 'C')
{
a[rt<<] = col[rt<<] = ;
}
if(R > mid)
{
update(val,L,R,mid+,r,rt<<|);
}
else if(val == 'I' || val == 'C')
{
a[rt<<|] = col[rt<<|] = ;
}
}
if判断左边是否小于mid，如果不是，那么更新它的左边就是我们想要的选中区域外了，右边同理。
第二个是有两种更新方式，覆盖和异或
这种问题一般需要两种标记，但这里其中一种是覆盖，所以一种标记可以用值自身表示，-1表示杂，非-1表示纯。一个标记数组就行。
然后还要理清两种标记使用的方式
很明显我们可以知道这个性质:
当一个区间被覆盖后,不管之前有没有异或标记都没有意义了
所以当一个节点得到覆盖标记时把异或标记清空
第三种是开闭区间，这里可以通过把所有数乘2处理(偶数表示端点,奇数表示两端点间的区间)。
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!\n")
#define MAXN 65535*2
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f int n,m; int a[MAXN<<],col[MAXN<<],ans; bool vis[MAXN]; void FXOR(int x)
{
if(a[x]!=-) a[x]^=;
else col[x]^=;
} void PushDown(int rt)
{
if(a[rt] != -)
{
a[rt<<] = a[rt<<|] = a[rt];
col[rt<<] = col[rt<<|] = ;
a[rt] = -;
}
if(col[rt])
{
FXOR(rt<<);
FXOR(rt<<|);
col[rt] = ;
}
} void update(char val,int L,int R,int l,int r,int rt)
{
if(L <= l && r <= R)
{
if(val == 'U')
{
a[rt] = ;
col[rt] = ;
}
else if(val == 'D')
{
a[rt] = col[rt] = ;
}
else if(val == 'C' || val == 'S')
{
FXOR(rt);
}
return;
}
PushDown(rt);
int mid = (l + r)>>;
if (L <= mid)
{
update(val,L,R,l,mid,rt<<);
}
else if(val == 'I' || val == 'C')
{
a[rt<<] = col[rt<<] = ;
}
if(R > mid)
{
update(val,L,R,mid+,r,rt<<|);
}
else if(val == 'I' || val == 'C')
{
a[rt<<|] = col[rt<<|] = ;
}
} void query(int l,int r,int rt)
{
if(a[rt] == )
{
for(int i = l;i<=r;i++) vis[i] = true;
return;
}
else if(a[rt] == ) return;
if(l == r) return;
PushDown(rt);
int mid = (l + r)>>;
query(l,mid,rt<<);
query(mid+,r,rt<<|);
} int main()
{
int r,t;
char op,lchar,rchar;
a[] = col[] = ;
while(~sf("%c %c%d,%d%c\n",&op,&lchar,&r,&t,&rchar))
{
r<<=;
t<<=;
if(lchar == '(') r++;
if(rchar == ')') t--;
update(op,r,t,,MAXN,);
}
query(,MAXN,);
int s = -,e;
bool flag = false;
for(int i=;i<=MAXN;i++)
{
if(vis[i])
{
if(s == -) s = i;
e = i;
}
else
{
if(s!=-)
{
if(flag) pf(" ");
pf("%c%d,%d%c",s&?'(':'[',s>>,(e+)>>,e&?')':']');
s = -;
flag = true;
}
}
}
if(!flag) printf("empty set");
return ; }