pojHelp with Intervals線段樹解法

pojHelp with Intervals線段樹解法

題：點擊打開鏈接

分析：稍加分析一下交並關系，很好理解。要求掌握線段樹區間更新。注意幾點：由於是連續的集合，而線段樹是節點，所以要將集合擴大兩倍以便用點表示。注意輸入[0,x)（x是任意大於0的數）即a（左邊）為0，並且包含，當處理0到a-1時a-1為-1，會報RE。

此處用到延遲標記col，col=0時將標記的區間更新為0；col為1時將區間更新為1；col為2時將區間翻轉。其中col為2時翻轉操作1-col表示：當col為0時會翻轉為1；當col為1時會翻轉為0；當col為-1（不用作處理）時，col變為2繼續翻轉；當col為2時（翻轉）col會變成-1（翻轉兩次即不處理）。這樣的標記操作在另一道題Sequence operation中表現的淋漓盡致。

詳細見代碼。

代碼：

#include
#include
#define lc (rt<<1)
#define rc (rt<<1|1)
#define lson l, m, lc
#define rson m + 1, r, rc
using namespace std;
const int maxn = 132000;
int col[maxn<<2];
/****************************
*******對延遲標記的操作******
****************************/
void PushDown(int rt){
    if(col[rt] == 2){
        col[rt] = 1 - col[rt];
        col[lc] = 1 - col[lc];
        col[rc] = 1 - col[rc];
    }
    if(~col[rt]){
		col[lc] = col[rc] = col[rt];
		col[rt] = -1;
	}
}
/**************************************
update更新
add等於0時，將L到R區間更新為0
add等於1時，將L到R區間更新為1
add等於2時，將L到R區間翻轉（1 - col）
1-col:
當col為0時會翻轉為1
當col為1時會翻轉為0
當col為-1（不用作處理）時，col變為2繼續翻轉
當col為2時（翻轉）col會變成-1（翻轉兩次即不處理）
**************************************/
void update(int L, int R, int add, int  l, int r, int rt){
	if(L <= l && r <= R){
		if(add == 2) col[rt] = 1 - col[rt];
		else col[rt] = add;
		return;
	}
	int m = l + r >> 1;
	PushDown(rt);
	if (L <= m) update(L, R, add, lson);
	if (R > m) update(L, R, add, rson);
}
/**************************************
*****查詢target節點的標記為0還是1******
   當l==r時col[rt]只會是0或1，不會是2，
因為col初始化為0,1-0或1-（1-0）不會等於2
***************************************/
int query(int tar, int l, int r, int rt){
    if(l == r) return col[rt];
    int m = r + l >> 1;
    PushDown(rt);
    if(tar <= m) return query(tar, lson);
    else return query(tar, rson);
}

int main(){
    int a, b;
    char str, lstr, mstr, rstr;
    memset(col, 0, sizeof(col));
    while(~scanf(" %c %c%d %c%d %c", &str, &lstr, &a, &mstr, &b, &rstr)){//簡單處理一下輸入
        a <<= 1;
        b <<= 1;
        if(lstr == '(') a++;
        if(rstr == ')') b--;
        if(str == 'U') update(a, b, 1, 0, maxn, 1);//將a到b區間更新成1
        if(str == 'I'){
            if(a <= 0) a = 1;//注意點：a-1要大於等於0（b可不考慮，因為maxn大於數據范圍）
            update(0, a - 1, 0, 0, maxn, 1);//將0到a-1區間更新成0
            update(b + 1, maxn, 0, 0, maxn, 1);
        }
        if(str == 'D') update(a, b, 0, 0, maxn, 1);
        if(str == 'C'){
            update(a, b, 2, 0, maxn, 1);//將a到b區間翻轉更新
            if(a <= 0) a = 1;
            update(0, a - 1, 0, 0, maxn, 1);
            update(b + 1, maxn, 0, 0, maxn, 1);
        }
        if(str == 'S') update(a, b, 2, 0, maxn, 1);
    }
    int k = 1, num = 0;
    for(int i = 0; i < maxn; i++){//簡單處理一下輸出
        int key = query(i, 0, maxn, 1);
        if(k && key){
            num++;
            k = 0;
            if(i&1) printf("(%d", i/2);
            else printf("[%d", i/2);
        }
        if(!k && !key){
            k = 1;
            i--;
            if(i&1) printf(",%d) ", (i + 1)>>1);
            else printf(",%d] ", (i + 1)>>1);
        }
    }
    if(!num) printf("empty set\n");
    return 0;
}