poj 3225 Help with Intervals

Description Input Output Sample Input Sample Output  

#include <cstdio>
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 65535*2+10;
int cover[maxn<<2],xorm[maxn<<2];
bool hash[maxn+10];
void fxor(int rt){
  if (cover[rt] != -1) cover[rt] ^= 1;
  else xorm[rt] ^= 1;
}
void PushDown(int rt){
  if (cover[rt] != -1){
    cover[rt<<1] = cover[rt<<1|1] = cover[rt];
    xorm[rt<<1] = xorm[rt<<1|1] = 0; cover[rt] = -1; // there has been a BUG.
  }
  if (xorm[rt]){
    fxor(rt<<1); fxor(rt<<1|1); xorm[rt] = 0;
  }
}
void update(char op, int L, int R, int l, int r, int rt){
  if (L <= l && R >= r){
    if (op == 'U') {cover[rt] = 1; xorm[rt] = 0;}
    else if (op == 'D') {cover[rt] = 0; xorm[rt] = 0;}
    else if (op == 'C' || op == 'S') {
      if (cover[rt] != -1) cover[rt] ^= 1;
      else xorm[rt] ^= 1;
    }
    return;
  }
  PushDown(rt); int m = (l + r) >> 1;
  if (L <= m) update(op, L, R, lson);
  else if (op == 'I' || op == 'C'){cover[rt<<1] = xorm[rt<<1] = 0;}
  if (R > m) update(op, L, R, rson);
  else if (op == 'I' || op == 'C'){cover[rt<<1|1] = xorm[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; // there had been a BUG.
  }
  else if (cover[rt] == 0) return;
  if (l == r) return;
  PushDown(rt); int m = (l + r) >> 1;
  query(lson); query(rson);
}
int main(void){
  char op, l, r; int a, b;
  cover[1] = xorm[1] = 0;
#ifndef ONLINE_JUDGE
  freopen("poj3225.in", "r", stdin);
#endif
  while (~scanf("%c %c%d,%d%c\n", &op, &l, &a, &b, &r)){
    a <<= 1; b <<= 1; if (l == '(') a++; if (r == ')') b--;
    if (a > b) { // there has been a BUG.
      if (op == 'I' || op == 'C') cover[1] = xorm[1] = 0;
    }
    else update(op, a, b, 0, maxn, 1);
  }
  query(0, maxn, 1); bool mrk = false; int start = -1, end;
  for (int i = 0; i <= maxn; ++i){
    if (hash[i]){
      if (start == -1) start = i;
      end = i;
    }
    else {
      if (start != -1){
        if (mrk) printf(" ");
        mrk = true;
        printf("%c%d,%d%c", start&1?'(':'[', start>>1, (end+1)>>1,end&1?')':']');
        start = -1;
      }
    }
  }
  if (!mrk) printf("empty set");
  printf("\n");
  return 0;
}

线段树，成段更新