题意：给你一些区间操作，让你输出最后得出的区间。
解法：区间操作的经典题，借鉴了网上的倍增算法，每次将区间乘以2，然后根据区间开闭情况做微调，这样可以有效处理开闭区间问题。
线段树维护两个值： cov 和 rev ，一个是覆盖标记，0表示此区间被0覆盖，1表示被1覆盖，-1表示未被覆盖， rev为反转标记，rev = 1表示反转，0表示不翻转
所以集合操作可以化为如下区间操作：
U l r: 把区间[l,r]覆盖成1
I l r: 把[0,l)(r,MAX]覆盖成0
D l r: 把区间[l,r]覆盖成0
C l r: 把[0,l)(r,MAX]覆盖成0 , 且[l,r]区间0/1互换
S l r: [l,r]区间0/1互换
重点在于pushdown函数以及边界处理。
代码：
#include <iostream>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N (65536*2) struct Tree
{
int cov,rev; //cov -1 rev 0
}tree[*N]; struct ANS
{
char L,R;
int A,B;
}ans[N+];
int cnt; void build(int l,int r,int rt)
{
tree[rt].cov = ;
tree[rt].rev = ;
if(l == r) return;
int mid = (l+r)/;
build(l,mid,*rt);
build(mid+,r,*rt+);
} void pushdown(int l,int r,int rt)
{
if(tree[rt].cov != -)
{
tree[*rt].cov = tree[*rt+].cov = tree[rt].cov;
tree[*rt].rev = tree[*rt+].rev = ;
tree[rt].cov = -;
}
if(tree[rt].rev)
{
if(tree[*rt].cov != -)
tree[*rt].cov ^= ;
else
tree[*rt].rev ^= ; if(tree[*rt+].cov != -)
tree[*rt+].cov ^= ;
else
tree[*rt+].rev ^= ;
tree[rt].rev = ;
}
} void update(int l,int r,int aa,int bb,int op,int rt)
{
if(aa > bb || aa < ) return; //必须要加，否则会RE
if(aa <= l && bb >= r)
{
if(op != ) //cover to 0/1
{
tree[rt].cov = op;
tree[rt].rev = ;
}
else //op == 2 reverse
{
if(tree[rt].cov != -)
tree[rt].cov ^= ;
else
tree[rt].rev ^= ;
}
return;
}
pushdown(l,r,rt);
int mid = (l+r)/;
if(aa <= mid)
update(l,mid,aa,bb,op,*rt);
if(bb > mid)
update(mid+,r,aa,bb,op,*rt+);
} void query(int l,int r,int rt)
{
if(tree[rt].cov == )
{
ans[cnt].L = (l%==)?'(':'[';
ans[cnt].A = l/;
ans[cnt].R = (r%==)?')':']';
ans[cnt].B = (r+)/;
cnt++;
}
else if(tree[rt].cov == ) return;
else
{
pushdown(l,r,rt);
int mid = (l+r)/;
query(l,mid,*rt);
query(mid+,r,*rt+);
}
} void print()
{
char nowl,nowr;
int nowA,nowB;
if(cnt == )
puts("empty set");
else
{
nowl = ans[].L;
nowr = ans[].R;
nowA = ans[].A;
nowB = ans[].B;
for(int i=;i<cnt;i++)
{
if(ans[i].A == nowB && (nowr == ']' || ans[i].L == '['))
{
nowB = ans[i].B;
nowr = ans[i].R;
}
else
{
printf("%c%d,%d%c ",nowl,nowA,nowB,nowr);
nowl = ans[i].L;
nowr = ans[i].R;
nowA = ans[i].A;
nowB = ans[i].B;
}
}
printf("%c%d,%d%c\n",nowl,nowA,nowB,nowr);
}
} int main()
{
int a,b;
char L,R,op;
int n = *;
build(,n,);
while(scanf("%c %c%d,%d%c\n",&op,&L,&a,&b,&R)!=EOF) // '\n' 务必要加
{
a = *a; if(L == '(') a++;
b = *b; if(R == ')') b--;
if(a > b || a < ) continue;
if(op == 'U') //并集
update(,n,a,b,,);
else if(op == 'I')
{
update(,n,,a-,,);
update(,n,b+,n,,);
}
else if(op == 'D')
update(,n,a,b,,);
else if(op == 'C')
{
update(,n,,a-,,);
update(,n,b+,n,,);
update(,n,a,b,,);
}
else
update(,n,a,b,,);
}
cnt = ;
query(,n,);
print();
return ;
}