poj3225（線段樹求區間交,並,補）

題目鏈接：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;
}