【Bzoj3226】校门外的区间

来源和评测点

Sdoi2008
Bzoj3226

从小白的角度解释本题

题目

【题目大意】
5种运算维护集合S(S初始为空)并最终输出S
5种运算如下:
U T:S、T并集
I T:S、T交集
D T:S独有
C T:T独有
S T:S独有 交 T独有
【输入格式】
输入共M行。
每行的格式为X T,用一个空格隔开,X表示运算的种类,T为一个区间

1
2
3
4
5
0≤a≤b≤65535,1≤M≤70000
**【输出格式】**
共一行,即集合S,每个区间后面带一个空格。
若S为空则输出"empty set"。
**【输入样例】**

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
**【输出样例】**
(2,3)
</p>
## 刷题记录
1h
3WA
1PE
1AC
## 分析
挺考验逻辑关系能力的
首先,区间都是连续的。
然后先消除区间表达法的多样性,可以考虑用t表示t/2,
这样把区间统一转化,例如(2,5)变成```[2.5,4.5]```也就是```[5,9]

然后各种操作逐个击破
U 区间1
I 独有0
D 区间0
C 区间取反,其余0
S 区间取反

各种max,min乱搞
线段树维护就好了

格式错误的话,是因为我以为打空格的同时换行,
当时就想为什么这么奇怪,原来不用换行。

然后WA的话,就是【可能我的方式太古怪了】除了打修改的时候删掉翻转外,
【因为我是用父亲c更新儿子c的】,所以如果翻转之前有修改标记而且是统一的(不是-1),
那么就不用往下打标记了

然后我的答案统计方式好像很独特啊,网上那些方法我看不懂……

最后最后就是,无数次忘记,翻转标记要用异或更新。

代码

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//*******************全局常量*******************
//*******************全局定义*******************
struct seg
{
int l,r;
int lc,rc;
int c;//-1,0,1
bool tg1,tg2;
}p[310000];
//*******************实现*******************
int ln=0;
int build(int l,int r)
{
int t=++ln;
p[t].l=l;p[t].r=r;p[t].c=0;
p[t].tg1=p[t].tg2=0;
if(l<r)
{
int mid=(l+r)/2;
p[t].lc=build(l,mid);
p[t].rc=build(mid+1,r);
}
else p[t].lc=p[t].rc=0;
return t;
}
void update(int x)
{
int lc=p[x].lc,rc=p[x].rc;
if(p[lc].c==p[rc].c) p[x].c=p[lc].c;
else p[x].c=-1;
}
void maketg1(int x,int c)
{
p[x].c=c;
p[x].tg1=1;
p[x].tg2=0;
}
void maketg2(int x)
{
if(p[x].c>=0) p[x].c=1-p[x].c;
if( !(p[x].tg1==1 and p[x].c>=0) ) p[x].tg2^=1;//debug
}
void pushdown(int x)
{
int lc=p[x].lc,rc=p[x].rc;
if(p[x].tg1>0)
{
p[x].tg1=0;
if(lc>0) maketg1(lc,p[x].c);
if(rc>0) maketg1(rc,p[x].c);
}
if(p[x].tg2>0)
{
p[x].tg2=0;
if(lc>0) maketg2(lc);
if(rc>0) maketg2(rc);
}
}
void change1(int x,int l,int r,int c)
{
if(x==0 or l>r) return;
if(p[x].l==l and p[x].r==r)
{
maketg1(x,c);
return;
}
pushdown(x);
int mid=(p[x].l+p[x].r)/2;
int lc=p[x].lc,rc=p[x].rc;
if(r<=mid) change1(lc,l,r,c);
else if(l>mid) change1(rc,l,r,c);
else change1(lc,l,mid,c),change1(rc,mid+1,r,c);
update(x);
}
void change2(int x,int l,int r)
{
if(x==0 or l>r) return;
pushdown(x);//debug
if(p[x].l==l and p[x].r==r)
{
maketg2(x);
return;
}
int mid=(p[x].l+p[x].r)/2;
int lc=p[x].lc,rc=p[x].rc;
if(r<=mid) change2(lc,l,r);
else if(l>mid) change2(rc,l,r);
else change2(lc,l,mid),change2(rc,mid+1,r);
update(x);
}
bool bk=0;
void output(int a,int b)
{
bk=1;
if(a%2==0) printf("[%d,",a/2);
else printf("(%d,",a/2);
if(b%2==0) printf("%d] ",b/2);
else printf("%d) ",b/2+1);
}
int ll=-2,rr=-2;
void ask(int x)
{
if(x==0) return;
if(p[x].c==1)
{
int a=p[x].l,b=p[x].r;
if(a>rr+1)
{
if(ll>=0) output(ll,rr);
ll=a;
}
rr=b;
}
if(p[x].c==-1)
{
pushdown(x);
ask(p[x].lc);
ask(p[x].rc);
}
}
//*******************主函数*******************
int main()
{
build(0,140000);
//build(0,10);
char s[5],c1,c2;int a,b;
while(scanf("%s %c%d,%d%c",s,&c1,&a,&b,&c2)!=EOF and s[0]!='e')
{
a*=2;if(c1=='(') a++;
b*=2;if(c2==')') b--;
if(s[0]=='U')
{
change1(1,a,b,1);
}
if(s[0]=='I')
{
change1(1,0,a-1,0);
change1(1,b+1,140000,0);
//change1(1,b+1,10,0);
}
if(s[0]=='D')
{
change1(1,a,b,0);
}
if(s[0]=='C')
{
change1(1,0,a-1,0);
change2(1,a,b);
change1(1,b+1,140000,0);
//change1(1,b+1,10,0);
}
if(s[0]=='S')
{
change2(1,a,b);
}
}
ask(1);if(ll>=0) output(ll,rr);
if(bk==0) printf("empty set");
}
/*
U 区间1
I 其余0
D 区间0
C 区间取反,其余0
S 区间取反
*/

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ef13.html
转载请注明出处,谢谢!