shabi题....bzoj关键字检查freopen??可怕,,1A的卡了一小时....
3226: [Sdoi2008]校门外的区间
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 624 Solved: 230
[Submit][Status][Discuss]
Description
受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出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)
Input
输入共M行。
每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。
Output
共一行，即集合S，每个区间后面带一个空格。若S为空则输出”empty set”。
Sample Input
U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]
Sample Output
(2,3)
HINT
对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000
Source
线段树
这道题shabi题..
可以认为是染色问题
U 区间涂1
I 两侧区间涂0
D 区间涂0
C 两侧涂0,中间取反
S 区间取反
然后线段树乱搞就行…
然后至于开闭区间问题,可以类似的把每个点拆成两个,加以判断即可,即[1,3]=[1,3],[1,3)=[1,2.5]当然程序中不是这么拆的,只是拆乘整数
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn (65535*2+10)
int read()
{
int x=0,f=0; char ch=getchar();
while(ch<'0' || ch>'9') { if (ch=='(') f=-1; ch=getchar();}
while(ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
if(ch==')') f=1;
return x*2-f;
}
int tree[maxn<<2],del[maxn<<2]={-1},rev[maxn<<2]={0};
void pushdown(int now,int l,int r)
{
if (l==r)
{
if (del[now]!=-1)
tree[now]=del[now];
tree[now]=tree[now]^rev[now];
rev[now]=0;del[now]=-1;
return;
}
if (del[now]!=-1)
{
del[now<<1]=del[now<<1|1]=del[now];
rev[now<<1|1]=rev[now<<1]=0;
}
rev[now<<1]=rev[now<<1]^rev[now];
rev[now<<1|1]=rev[now<<1|1]^rev[now];
rev[now]=0;del[now]=-1;
}
void change(int L,int R,int now,int l,int r,int opt)
{
if (R<L) return;
pushdown(now,l,r);
if(L<=l && R>=r)
{
if (opt==-1) {rev[now]=rev[now]^1;}
else {del[now]=opt;}
return;
}
int mid=(l+r)>>1;
if (L<=mid)
change(L,R,now<<1,l,mid,opt);
if (R>mid)
change(L,R,now<<1|1,mid+1,r,opt);
}
int get(int now,int l,int r,int loc)
{
pushdown(now,l,r);
if (l==r)
return tree[now];
int mid=(l+r)>>1;
if (loc<=mid) return get(now<<1,l,mid,loc);
else return get(now<<1|1,mid+1,r,loc);
}
void work()
{
char opt[10];int l,r;
while (scanf("%s",opt)!=EOF)
{
l=read(),r=read();
l+=2;r+=2;
switch (opt[0])
{
case 'U' : change(l,r,1,1,maxn,1);break;
case 'I' : change(1,l-1,1,1,maxn,0);change(r+1,maxn,1,1,maxn,0);break;
case 'D' : change(l,r,1,1,maxn,0);break;
case 'C' : change(1,l-1,1,1,maxn,0);change(r+1,maxn,1,1,maxn,0);change(l,r,1,1,maxn,-1);break;
case 'S' : change(l,r,1,1,maxn,-1);break;
}
}
}
void prin()
{
int l=-1,r=-1,f=0;
for(int i=1;i<=maxn;i++)
if(get(1,1,maxn,i))
{
if (l==-1) l=i;
r=i;
}
else
{
if(l!=-1)
{
if (f) printf(" ");
else f=1;
if (l&1) printf("(");
else printf("[");
printf("%d",l/2-1);
printf(",");
printf("%d",(r+1)/2-1);
if (r&1) printf(")");
else printf("]");
}
l=-1,r=-1;
}
if(!f) puts("empty set");
}
int main()
{
//freopen("BZOJ3226.in","r",stdin);
work();
prin();
return 0;
}