学步园

U:把区间[l,r]覆盖成1

I:把[-∞,l)(r,∞]覆盖成0

D:把区间[l,r]覆盖成0

C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换

S:[l,r]区间0/1互换

这是一个关键的提示，然后把区间扩大并线段树维护0或1，这题好复杂。

/****************************************************/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <stack>
#include <map>
#include <queue>
#include <algorithm>
#include <ctime>
#define EPS 1E-8
#define MAXN 70000 << 1
#define MAXM 31
#define INF (~0U >> 2)
#define MOD 1000000007
#define Lson l, mid, rt << 1
#define Rson mid + 1, r, rt << 1 | 1
using namespace std;
typedef long long LL;
/****************************************************/
int col[MAXN << 2], Xor[MAXN << 2], hash[MAXN], res;
void do_xor(int rt)
{
	if (col[rt] != -1)
		col[rt] ^= 1;
	else
		Xor[rt] ^= 1;
}
void push_down(int rt)
{
	if (col[rt] != -1)
	{
		col[rt << 1] = col[rt << 1 | 1] = col[rt];
		Xor[rt << 1] = Xor[rt << 1 | 1] = 0;
		col[rt] = -1;
	}
	if (Xor[rt])
	{
		do_xor(rt << 1);
		do_xor(rt << 1 | 1);
		Xor[rt] = 0;
	}
}
void update(int L, int R, int C, int l, int r, int rt)
{
	if (L <= l && r <= R)
	{
		if (C == 'U')
		{
			col[rt] = 1;
			Xor[rt] = 0;
		}
		else if (C == 'D')
		{
			col[rt] = 0;
			Xor[rt] = 0;
		}
		else if (C == 'C' || C == 'S')
		{
			do_xor(rt);
		}
		return;
	}
	push_down(rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(L, R, C, Lson);
	else if (C == 'I' || C == 'C')
		Xor[rt << 1] = col[rt << 1] = 0; //区间外置0
	if (R > mid)
		update(L, R, C, Rson);
	else if (C == 'I' || C == 'C')
		Xor[rt << 1 | 1] = col[rt << 1 | 1] = 0; //区间外置0
}
void query(int l, int r, int rt)
{
	if (col[rt] == 1)
	{
		for (int i = l; i <= r; i++)
			hash[i] = 1;
		return;
	}
	if (col[rt] == 0 || l == r)
		return;
	push_down(rt);
	int mid = (l + r) >> 1;
	query(Lson);
	query(Rson);
}
char C;
int main()
{
	col[1] = Xor[1] = 0;
	while (scanf("%c", &C) != EOF)
	{
		getchar();
		char c1, c2, c0;
		int a, b;
		scanf("%c%d%c%d%c%c", &c1, &a, &c0, &b, &c2, &c0);
		a <<= 1; b <<= 1;
		if (c1 == '(')
			a++;
		if (c2 == ')')
			b--;
		update(a, b, C, 0, MAXN, 1);
	}
	query(0, MAXN, 1);
	int flag = 0, s = -1, e;
	for (int i = 0; i <= MAXN; i++)
	{
		if (hash[i])
		{
			if (s == -1)
				s = i;
			e = i;
		}
		else if (s != -1)
		{
			if (flag)
				printf (" ");
			flag = 1;
			char c1, c2;
			if (s & 1)
				c1 = '(';
			else
				c1 = '[';
			if (e & 1)
				c2 = ')';
			else
				c2 = ']';
			printf("%c%d,%d%c", c1, s >> 1, (e + 1) >> 1, c2);
			s = -1;
		}
	}
	if (!flag)
		printf("empty set");
	puts("");
}