题目大意:有5种运算维护集合S(S初始为空)并最终输出S。
5种运算如下:
U T S∪T
I T S∩T
D T S-T
C T T-S
S T S⊕T
基本集合运算如下:
A∪B
{x : xÎA or xÎB}
A∩B
{x : xÎA and xÎB}
A-B
{x : xÎA and xÏB}
A⊕B
(A-B)∪(B-A)
思路::每个数之间加入一个数,就像这样2 2.5 3 3.5 4 [2,3) -> [2,2.5] (3,4] -> [3.5,4] 用01表示集合,则U 区间涂1;I 两侧区间涂0;D 区间涂0;C 两侧涂0,中间取反;S 区间取反。用线段树解决,标记的下传很重要(被坑了)。
代码:
#include<cstdio>
#include<iostream>
#define n 131073
using namespace std;
int lazy[n<<2],num[n<<2],rev[n<<2];
int read()
{
int x=0,y=0;
char ch=getchar();
while (ch<'0' || ch>'9')
{
if (ch=='(') y=1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-48;
ch=getchar();
}
if (ch==')') y=-1;
return x*2+y+2;
}
void push_down(int x,int l,int r)
{
int y=lazy[x],z=rev[x];
lazy[x]=-1,rev[x]=0;
if (l==r)
{
if (y!=-1) num[x]=y;
num[x]^=z;
return;
}
if (y!=-1)
{
lazy[x<<1]=lazy[x<<1|1]=y;
rev[x<<1]=rev[x<<1|1]=0;
}
rev[x<<1]^=z,rev[x<<1|1]^=z;
}
void add(int L,int R,int l,int r,int cur,int val)
{
if (l>r) return;
push_down(cur,L,R);
if (l<=L && r>=R)
{
if (val<2) lazy[cur]=val;
else rev[cur]^=1;
return;
}
int mid=L+R>>1;
if (l>mid) add(mid+1,R,l,r,cur<<1|1,val);
else if (r<=mid) add(L,mid,l,r,cur<<1,val);
else add(L,mid,l,mid,cur<<1,val),add(mid+1,R,mid+1,r,cur<<1|1,val);
}
int ask(int l,int r,int x,int cur)
{
push_down(cur,l,r);
if (l==r) return num[cur];
int mid=l+r>>1;
if (x<=mid) return ask(l,mid,x,cur<<1);
else return ask(mid+1,r,x,cur<<1|1);
}
int main()
{
char ch[9];
for (int i=0;i<=n*4;i++) lazy[i]=-1;
while (scanf("%s",ch)!=EOF)
{
int a=read(),b=read();
if (ch[0]=='U') add(1,n,a,b,1,1);
if (ch[0]=='I') add(1,n,1,a-1,1,0),add(1,n,b+1,n,1,0);
if (ch[0]=='D') add(1,n,a,b,1,0);
if (ch[0]=='C') add(1,n,1,a-1,1,0),add(1,n,a,b,1,2),add(1,n,b+1,n,1,0);
if (ch[0]=='S') add(1,n,a,b,1,2);
}
int h=0,t=0,flag=0;
for (int i=1;i<=n;i++)
if (ask(1,n,i,1))
{
if (!h) h=i;
t=i;
}
else
{
if (h)
{
if (flag) printf(" ");
else flag=1;
if (h&1) printf("(");
else printf("[");
printf("%d,%d",h/2-1,(t+1)/2-1);
if (t&1) printf(")");
else printf("]");
}
h=t=0;
}
if (!flag) printf("empty set");
else printf(" ");
return 0;
}