poj 3225 Help with Intervals

模版题，线段树区间赋值，反转，看别人代码敲的；
  1 #include<stdio.h>
  2 #include<string.h>
  3 #define MAXD 132000
  4 #define N 131070
  5 int tree[4 * MAXD], rev[4 * MAXD], to[4 * MAXD], a[MAXD];
  6 void build(int cur, int x, int y)
  7 {
  8     int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;
  9     tree[cur] = rev[cur] = 0;
 10     to[cur] = -1;
 11     if(x == y)
 12         return ;
 13     build(ls, x, mid);
 14     build(rs, mid + 1, y);
 15 }
 16 void pushdown(int cur)
 17 {
 18     int ls = cur << 1, rs = (cur << 1) | 1;
 19     if(to[cur] != -1)
 20     {
 21         to[ls] = to[rs] = to[cur];
 22         rev[ls] = rev[rs] = 0;
 23         tree[ls] = tree[rs] = to[cur];
 24         to[cur] = -1;
 25     }
 26     if(rev[cur])
 27     {
 28         rev[ls] = (rev[ls] + 1) & 1, rev[rs] = (rev[rs] + 1) & 1;
 29         tree[ls] ^= 1, tree[rs] ^= 1;
 30         rev[cur] = 0;
 31     }
 32 }
 33 void color(int cur, int x, int y, int s, int t, int c)
 34 {
 35     int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;
 36     if(x >= s && y <= t)
 37     {
 38         tree[cur] = to[cur] = c;
 39         rev[cur] = 0;
 40         return ;
 41     }
 42     pushdown(cur);
 43     if(mid >= s)
 44         color(ls, x, mid, s, t, c);
 45     if(mid + 1 <= t)
 46         color(rs, mid + 1, y, s, t, c);
 47 }
 48 void Reverse(int cur, int x, int y, int s, int t)
 49 {
 50     int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;
 51     if(x >= s && y <= t)
 52     {
 53         tree[cur] ^= 1;
 54         rev[cur] = (rev[cur] + 1) & 1;
 55         return ;
 56     }
 57     pushdown(cur);
 58     if(mid >= s)
 59         Reverse(ls, x, mid, s, t);
 60     if(mid + 1 <= t)
 61         Reverse(rs, mid + 1, y, s, t);
 62 }
 63 void dfs(int cur, int x, int y)
 64 {
 65     int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;
 66     if(x == y)
 67     {
 68         a[x] = tree[cur];
 69         return ;
 70     }
 71     pushdown(cur);
 72     dfs(ls, x, mid);
 73     dfs(rs, mid + 1, y);
 74 }
 75 void printresult()
 76 {
 77     int i, x, y, flag = 0;
 78     dfs(1, 0, N);
 79     for(i = 0; i <= N; i ++)
 80     {
 81         if(a[i])
 82         {
 83             if(flag)
 84                 printf(" ");
 85             else
 86                 flag = 1;
 87             if(i & 1)
 88                 printf("(%d,", i >> 1);
 89             else
 90                 printf("[%d,", i >> 1);
 91             for(; a[i + 1]; i ++);
 92             if(i & 1)
 93                 printf("%d)", (i + 1) >> 1);
 94             else
 95                 printf("%d]", i >> 1);
 96         }
 97     }
 98     if(flag == 0)
 99         printf("empty set\n");
100     printf("\n");
101 }
102 void solve()
103 {
104     int x, y;
105     char op[5], b[20];
106     while(scanf("%s%s", op, b) == 2)
107     {
108         sscanf(b + 1, "%d,%d", &x, &y);
109         if(b[0] == '(')
110             x = (x << 1) | 1;
111         else
112             x <<= 1;
113         if(b[strlen(b) - 1] == ')')
114             y = (y << 1) - 1;
115         else
116             y <<= 1;
117         if(op[0] == 'U')
118             color(1, 0, N, x, y, 1);
119         else if(op[0] == 'D')
120             color(1, 0, N, x, y, 0);
121         else if(op[0] == 'S')
122             Reverse(1, 0, N, x, y);
123         else if(op[0] == 'C')
124         {
125             if(x > 0)
126                 color(1, 0, N, 0, x - 1, 0);
127             if(y < N)
128                 color(1, 0, N, y + 1, N, 0);
129             Reverse(1, 0, N, x, y);
130         }
131         else
132         {
133             if(x > 0)
134                 color(1, 0, N, 0, x - 1, 0);
135             if(y < N)
136                 color(1, 0, N, y + 1, N, 0);
137         }
138     }
139     printresult();
140 }
141 int main()
142 {
143     build(1, 0, N);
144     solve();
145     return 0;
146 }