POJ 3225 Help with Intervals（線段樹）

POJ 3225 Help with Intervals

題目鏈接

集合數字有的為1，沒有為0，那么幾種操作相應就是置為0或置為1或者翻轉，這個隨便推推就能夠了，然后開閉區間的處理方式就是把區間擴大成兩倍，偶數存點，奇數存線段就可以

代碼：

#include <cstdio>
#include <cstring>#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)const int N = 65536 * 2;struct Node {int l, r, flip, setv;
} node[N * 4];int to[N];void build(int l, int r, int x = 0) {node[x].l = l; node[x].r = r;node[x].flip = 0; node[x].setv = -1;if (l == r) {to[l] = x;return;}int mid = (l + r) / 2;build(l, mid, lson(x));build(mid + 1, r, rson(x));
}void pushdown(int x) {if (node[x].setv != -1) {node[lson(x)].setv = node[rson(x)].setv = node[x].setv;node[lson(x)].flip = node[rson(x)].flip = 0;node[x].setv = -1;}if (node[x].flip) {node[lson(x)].flip ^= 1;node[rson(x)].flip ^= 1;node[x].flip = 0;}
}void add(int l, int r, int v, int x = 0) {if (l > r) return;if (node[x].l >= l && node[x].r <= r) {if (v != -1) {node[x].setv = v;node[x].flip = 0;} elsenode[x].flip ^= 1;return;}pushdown(x);int mid = (node[x].l + node[x].r) / 2;if (l <= mid) add(l, r, v, lson(x));if (r > mid) add(l, r, v, rson(x));
}void query(int x = 0) {if (node[x].l == node[x].r) {if (node[x].setv == -1) node[x].setv = 0;return;}pushdown(x);int mid = (node[x].l + node[x].r) / 2;query(lson(x));query(rson(x));
}char c, a, b;
int l, r;int main() {build(0, N - 1);while (~scanf("%c %c%d,%d%c\n", &c, &a, &l, &r, &b)) {l = l * 2 + (a == '(');r = r * 2 - (b == ')');if (c == 'U') add(l, r, 1);if (c == 'I' || c == 'C') {add(0, l - 1, 0);add(r + 1, N - 1, 0);if (c == 'C') add(l, r, -1);}if (c == 'D') add(l, r, 0);if (c == 'S') add(l, r, -1);}query();int pre = 0, flag = 0, bo = 0;for (int i = 0; i < N; i++) {int id = to[i];int tmp = (node[id].setv^node[id].flip);if (!tmp && flag) {if (bo) printf(" ");else bo = 1;if (pre % 2) printf("(");else printf("[");printf("%d,%d", pre / 2, i / 2);if (i % 2 == 0) printf(")");else printf("]");flag = 0;} else if (tmp && !flag) {pre = i;flag = 1;}}if (bo == 0) printf("empty set");printf("\n");return 0;
}