题意：区间操作，交，并，补等
思路：
我们一个一个操作来分析：（用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互换
成段覆盖的操作很简单，比较特殊的就是区间0/1互换这个操作，我们可以称之为异或操作
很明显我们可以知道这个性质：当一个区间被覆盖后，
不管之前有没有异或标记都没有意义了
所以当一个节点得到覆盖标记时把异或标记清空
而当一个节点得到异或标记的时候，先判断覆盖标记，如果是0或1,
直接改变一下覆盖标记，不然的话改变异或标记
开区间闭区间只要数字乘以2就可以处理（偶数表示端点，奇数表示两端点间的区间）http://my.oschina.net/llmm/blog/124256
*/
#include
#include
#include
using namespace std;
#define lson l, m, rt《1
#define rson m+1, r, rt《1|1
const int N = 150000;
int cover[N《2];
int XOR[N《2];
bool hash[N《2];
void CXOR（int rt）
{
if（cover[rt] != -1） cover[rt] ^= 1;//有覆盖标记，直接修改覆盖标记
else XOR[rt] ^= 1;//无覆盖标记，修改异或标记
}
void pushdown（int rt）//更新子树
{
if（cover[rt] != -1）
{
cover[rt《1] = cover[rt《1|1] = cover[rt];
XOR[rt《1] = XOR[rt《1|1] = 0;
cover[rt] = -1;
}
if（XOR[rt]）
{
CXOR（rt《1）；
CXOR（rt《1|1）；
XOR[rt] = 0;
}
}
void update（int L, int R, char op, int l, int r, int rt）
{
if（L <= l && r <= R）
{
switch（op）
{
case 'U': cover[rt] = 1; XOR[rt] = 0; break;//把区间[l,r]覆盖成1,清除异或标记
case 'I': break;
case 'D': cover[rt] = 0; XOR[rt] = 0; break;//把区间[l,r]覆盖成0,清除异或标记
case 'C': CXOR（rt）；break;
case 'S': CXOR（rt）；break;
}
return;
}
pushdown（rt）；
int m = （l+r） 》 1;
if（L <= m） update（L, R, op, lson）；//更新左子树
else if（op == 'I' || op == 'C'）//I和C,都有将[-∞，l）（r,∞]覆盖成0的操作
cover[rt《1] = XOR[rt《1] = 0;
if（m < R） update（L, R, op, rson）；
else if（op == 'I' || op == 'C'）
cover[rt《1|1] = XOR[rt《1|1] = 0;
}
void query（int l, int r, int rt）
{
if（cover[rt] == 1）
{
for（int i = l; i <= r; i ++）
hash[i] = true;
return;
}
if（cover[rt] == 0） return;
pushdown（rt）；
int m = （l+r） 》 1;
query（lson）；
query（rson）；
}
int main（）
{
char op,b,c,d;
int x,y;
while（~scanf（"%c %c%d%c%d%c\n",&op,&b,&x,&c,&y,&d））
{
x 《= 1; y 《= 1;
if（b == '（'） x++;
if（d == '）'） y--;
if（x > y）//处理（1,1）这类区间
{
if（op == 'I' || op == 'C'）
cover = XOR = 0;
}
else
update（x, y, op, 0, N, 1）；
}
query（0, N , 1）；
int flag = 0;
x = -1;
for（int i = 0; i <= N; i ++）
{
if（hash[i]）
{
if（x == -1） x = i;
y = i;
}
else
{
if（x != -1）
{
if（flag） printf（" "）；
flag = 1;
printf（"%c%d,%d%c",x&1 '（':'[',x》1,（y+1）》1,y&1 '）':']'）；
x = -1;
}
}
}
if （！flag） printf（"empty set"）；
printf（"\n"）；
return 0;
} |