POJ_3225

    对于开区间还是闭区间的问题，可以把所有的点都乘以2，这样就可以通过偶数端点判断是闭区间，通过奇数端点判断开区间。

    剩下的问题就是用线段树实现区间染色和区间取反的操作了。

#include
     
       #include
      
        #define MAXD 132000 #define N 131070 int tree[4 * MAXD], rev[4 * MAXD], to[4 * MAXD], a[MAXD]; void build(int cur, int x, int y) {
   int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;     tree[cur] = rev[cur] = 0;     to[cur] = -1; if(x == y) return ;     build(ls, x, mid);     build(rs, mid + 1, y); } void pushdown(int cur) {
   int ls = cur << 1, rs = (cur << 1) | 1; if(to[cur] != -1)     {
           to[ls] = to[rs] = to[cur];         rev[ls] = rev[rs] = 0;         tree[ls] = tree[rs] = to[cur];         to[cur] = -1;     } if(rev[cur])     {
           rev[ls] = (rev[ls] + 1) & 1, rev[rs] = (rev[rs] + 1) & 1;         tree[ls] ^= 1, tree[rs] ^= 1;         rev[cur] = 0;     } } void color(int cur, int x, int y, int s, int t, int c) {
   int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x >= s && y <= t)     {
           tree[cur] = to[cur] = c;         rev[cur] = 0; return ;     }     pushdown(cur); if(mid >= s)         color(ls, x, mid, s, t, c); if(mid + 1 <= t)         color(rs, mid + 1, y, s, t, c); } void Reverse(int cur, int x, int y, int s, int t) {
   int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x >= s && y <= t)     {
           tree[cur] ^= 1;         rev[cur] = (rev[cur] + 1) & 1; return ;     }     pushdown(cur); if(mid >= s)         Reverse(ls, x, mid, s, t); if(mid + 1 <= t)         Reverse(rs, mid + 1, y, s, t); } void dfs(int cur, int x, int y) {
   int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x == y)     {
           a[x] = tree[cur]; return ;     }     pushdown(cur);     dfs(ls, x, mid);     dfs(rs, mid + 1, y); } void printresult() {
   int i, x, y, flag = 0;     dfs(1, 0, N); for(i = 0; i <= N; i ++)     {
   if(a[i])         {
   if(flag)                 printf(" "); else                 flag = 1; if(i & 1)                 printf("(%d,", i >> 1); else                 printf("[%d,", i >> 1); for(; a[i + 1]; i ++); if(i & 1)                 printf("%d)", (i + 1) >> 1); else                 printf("%d]", i >> 1);         }     } if(flag == 0)         printf("empty set\n");     printf("\n"); } void solve() {
   int x, y; char op[5], b[20]; while(scanf("%s%s", op, b) == 2)     {
           sscanf(b + 1, "%d,%d", &x, &y); if(b[0] == '(')             x = (x << 1) | 1; else             x <<= 1; if(b[strlen(b) - 1] == ')')             y = (y << 1) - 1; else             y <<= 1; if(op[0] == 'U')             color(1, 0, N, x, y, 1); else if(op[0] == 'D')             color(1, 0, N, x, y, 0); else if(op[0] == 'S')             Reverse(1, 0, N, x, y); else if(op[0] == 'C')         {
   if(x > 0)                 color(1, 0, N, 0, x - 1, 0); if(y < N)                 color(1, 0, N, y + 1, N, 0);             Reverse(1, 0, N, x, y);         } else         {
   if(x > 0)                 color(1, 0, N, 0, x - 1, 0); if(y < N)                 color(1, 0, N, y + 1, N, 0);         }     }     printresult(); } int main() {
       build(1, 0, N);     solve(); return 0; }