Poj3225Help with Intervals区间线段树

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include<math.h>
#include<vector>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn = 65545 * 2;
int color[maxn << 2], sign[maxn << 2];
int Hash[maxn << 2];
void gao(int rt)
{
    if (~color[rt]) color[rt] ^= 1;
    else sign[rt] ^= 1;
}

void down(int rt)
{
    if (~color[rt]){
        color[rt << 1] = color[rt << 1 | 1] = color[rt];
        sign[rt << 1] = sign[rt << 1 | 1] = 0;
        color[rt] = -1;
    }
    if (sign[rt]){
        gao(rt << 1); gao(rt << 1 | 1);
        sign[rt] = 0;
    }
}



void update(int L, int R, char c, int l, int r, int rt)
{
    if (L <= l&&r <= R){
        if (c == ‘U‘){
            color[rt] = 1; sign[rt] = 0;
        }
        if (c == ‘D‘){
            color[rt] = 0; sign[rt] = 0;
        }
        if (c == ‘C‘) gao(rt);
        if (c == ‘S‘) gao(rt);
        return;
    }
    down(rt);
    int mid = (l + r) >> 1;
    if (L <= mid) update(L, R, c, lson);
    else if (c == ‘I‘ || c == ‘C‘) color[rt << 1] = sign[rt << 1] = 0;
    if (mid<R) update(L, R, c, rson);
    else if (c == ‘I‘ || c == ‘C‘) color[rt << 1 | 1] = sign[rt << 1 | 1] = 0;
}

void ask(int l, int r, int rt)
{
    if (color[rt] == 1){
        for (int i = l; i <= r; i++)
            Hash[i] = 1;
        return;
    }
    if (l == r) return;
    if (color[rt] == 0) return;
    down(rt);
    int mid = (l + r) >> 1;
    ask(lson);
    ask(rson);
}

int main()
{
    char str[100], str1[100];
    int a; int b;
    char c2, c1;
    memset(Hash, 0, sizeof(Hash));
    color[1] = sign[1] = 0;
    while (scanf("%s %c%d,%d%c", str, &c1, &a, &b, &c2) != EOF){
        char c = str[0];
        a *= 2; b *= 2; if (c1 == ‘(‘) a++; if (c2 == ‘)‘) b--;
        update(a, b, c, 0, maxn, 1);
    }
    ask(0, maxn, 1);
    bool flag = false;
    int s = -1, t = -1;
    for (int i = 0; i <= maxn; ++i){
        if (Hash[i])s = (s == -1 ? i : s), t = i;
        else if (s != -1){
            if (flag)printf(" ");
            flag = true;
            printf("%c%d,%d%c", s & 1 ? ‘(‘ : ‘[‘, s >> 1, (t + 1) >> 1, t & 1 ? ‘)‘ : ‘]‘);
            s = -1;
        }
    }
    if (!flag)printf("empty set");
    printf("\n");
    return 0;
}