「BZOJ3226」[SDOI2008] 校门外的区间
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]
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
题解
来自zky：
每个数之间加入一个数,就像这样
2 2.5 3 3.5 4
[2,3) -> [2,2.5]
(3,4] -> [3.5,4]
U 区间涂1
I 两侧区间涂0
D 区间涂0
C 两侧涂0,中间取反
S 区间取反
线段树搞搞就可以了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> #define ll long long #define inf 1000000000 #define n (65536*2+1) using namespace std; 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; } char ch[5]; struct seg{int l,r,val,tag,rev;}t[4*n]; void build(int k,int l,int r) { t[k].l=l;t[k].r=r;t[k].tag=-1; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void pushdown(int k) { int tag=t[k].tag,rev=t[k].rev; t[k].tag=-1;t[k].rev=0; if(t[k].l==t[k].r) { if(tag!=-1) t[k].val=tag; t[k].val^=rev;; return; } if(tag!=-1) { t[k<<1].tag=t[k<<1|1].tag=tag; t[k<<1].rev=t[k<<1|1].rev=0; } t[k<<1].rev^=rev;t[k<<1|1].rev^=rev; } int query(int k,int x) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==r)return t[k].val; int mid=(l+r)>>1; if(x<=mid)return query(k<<1,x); else return query(k<<1|1,x); } void modify(int k,int x,int y,int val) { if(y<x)return; pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r) { if(val==-1)t[k].rev^=1; else t[k].tag=val; return; } int mid=(l+r)>>1; if(y<=mid)modify(k<<1,x,y,val); else if(x>mid)modify(k<<1|1,x,y,val); else { modify(k<<1,x,mid,val); modify(k<<1|1,mid+1,y,val); } } void rever(int k,int x,int y) { modify(k,x,y,-1); } int main() { build(1,1,n); while(scanf("%s",ch)!=EOF) { int a=read(),b=read(); a+=2;b+=2; switch(ch[0]) { case 'U':modify(1,a,b,1);break; case 'I':modify(1,1,a-1,0);modify(1,b+1,n,0);break; case 'D':modify(1,a,b,0);break; case 'C':modify(1,1,a-1,0);modify(1,b+1,n,0);rever(1,a,b);break; case 'S':rever(1,a,b);break; } } int start=-1,last=-1,flag=0; for(int i=1;i<=n;i++) if(query(1,i)) { if(start==-1)start=i; last=i; } else { if(start!=-1) { if(flag)printf(" "); else flag=1; if(start&1)printf("("); else printf("["); printf("%d",start/2-1); printf(","); printf("%d",(last+1)/2-1); if(last&1)printf(")"); else printf("]"); } last=start=-1; } if(!flag)puts("empty set"); return 0; } |
Subscribe
计数器 9794743
OI 课件=>
OI 课件=>