题目链接：poj3225
看了好久才看明白。。。。
/* 题意:区间操作,交,并,补等 思路: 我们一个一个操作来分析:(用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[1] = XOR[1] = 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; }