POJ_3225
对于开区间还是闭区间的问题，可以把所有的点都乘以2，这样就可以通过偶数端点判断是闭区间，通过奇数端点判断开区间。
剩下的问题就是用线段树实现区间染色和区间取反的操作了。
#include<stdio.h>
#include<string.h>
#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;
}