隐藏
「SCOI2007」降雨量 - 线段树 | Bill Yang's Blog
0%

「SCOI2007」降雨量 - 线段树

判断条件

对于三元组$\begin{pmatrix} y && z && x \end{pmatrix} ,z\in(y,x)$,满足y>=x&&x>=z,且$[y,x]$所有元素已知,则输出true,若有未知输出maybe,若不满足输出false


数据结构

因为本题信息为线性区间,为维护信息,我们可以采用线段树。
线段树维护4个信息:

  • leftyear:闭区间最左端表示的年份
  • rightyear:闭区间最右端表示的年份
  • max:区间中最大的降雨量
  • known:区间中的信息是否全部已知

区间合并时需注意:

  • leftyear:左儿子区间leftyear
  • rightyear:右儿子区间rightyear
  • max:max{左儿子区间max,右儿子区间max}
  • known:左儿子known&&右儿子known&&左儿子rightyear+1==右儿子leftyear

查询区间max与known与此合并方式类似,只需注意合并known时判断是否包含左右儿子区间,即:

1
2
3
return query_known(ls,Left,Right)&&query_known(rs,Left,Right)
&&(tree[ls].rightyear<Left||tree[rs].leftyear>Right
||tree[ls].rightyear+1==tree[rs].leftyear);


分类讨论

本题细节需要注意:

  • 询问区间的端点处降雨量未知
  • 前驱后继不存在
  • 左端点后继>右端点前驱
  • 区间左端点->区间左端点后继中有未知降雨量
  • 区间右端点前驱->区间右端点中有未知降雨量

考虑以上因素实现代码,流程图如下(P.S.流程图好像挂了,请放进markdown编辑器欣赏):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
st=>start: First
io=>inputoutput: left、right
op1=>operation: l=left年降雨量、r=right年降雨量
cond1=>condition: right<=left
cond2=>condition: l未知&&r未知
iot=>inputoutput: true
iof=>inputoutput: false
iom=>inputoutput: maybe
sub=>subroutine: Second
e=>end

st->io->op1->cond1
cond1(yes)->iof->e
cond1(no)->cond2
cond2(yes)->iom->e
cond2(no)->sub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
st=>start: Second
op1=>operation: l1=left后继、r1=right前驱
cond1=>condition: l未知
cond2=>condition: r未知
sub1=>subroutine: l未知
sub2=>subroutine: r未知
sub3=>subroutine: l、r已知
iot=>inputoutput: true
iof=>inputoutput: false
iom=>inputoutput: maybe
e=>end

st->op1->cond1
cond1(yes)->sub1
cond1(no)->cond2
cond2(yes)->sub2
cond2(no)->sub3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
st=>start: l未知
op1=>operation: ans=l1~r1最大值
cond1=>condition: l1>r1或r1不存在
cond2=>condition: ans>=r
iot=>inputoutput: true
iof=>inputoutput: false
iom=>inputoutput: maybe
iom2=>inputoutput: maybe
e=>end
e2=>end

st->cond1
cond1(yes)->iom->e
cond1(no)->op1->cond2
cond2(yes)->iof->e2
cond2(no)->iom2->e2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
st=>start: r未知
op1=>operation: ans=l1~r1最大值
cond1=>condition: l1>r1或l1不存在
cond2=>condition: ans>=l
iot=>inputoutput: true
iof=>inputoutput: false
iom=>inputoutput: maybe
iom2=>inputoutput: maybe
e=>end
e2=>end

st->cond1
cond1(yes)->iom->e
cond1(no)->op1->cond2
cond2(yes)->iof->e2
cond2(no)->iom2->e2
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
st=>start: l、r已知
op1=>operation: ans=l1~r1最大值
known=l1~r1是否已知
cond1=>condition: r>l
cond2=>condition: l1>r1
cond3=>condition: left+1==right
cond4=>condition: ans>=r
cond5=>condition: known==0
或left+1!=l1
或right-1!=r1
iot=>inputoutput: true
iof=>inputoutput: false
iof2=>inputoutput: false
iom=>inputoutput: maybe
iom2=>inputoutput: maybe
e=>end
e2=>end

st->cond1
cond1(yes)->iof->e
cond1(no)->cond2
cond2(yes)->cond3
cond2(no)->op1->cond4
cond3(yes)->iot->e2
cond3(no)->iom->e2
cond4(yes)->iof2->e2
cond4(no)->cond5
cond5(yes)->iom2->e2
cond5(no)->iot

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<ctime>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=50005;
struct Tree {
int leftyear,rightyear,max;
bool known;
Tree() {}
Tree(int ly,int ry,int m,bool k):leftyear(ly),rightyear(ry),max(m),known(k) {}
};
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void push_up(int index) {
tree[index].leftyear=tree[ls].leftyear;
tree[index].rightyear=tree[rs].rightyear;
tree[index].max=max(tree[ls].max,tree[rs].max);
tree[index].known=tree[ls].known&&tree[rs].known&&(tree[ls].rightyear+1==tree[rs].leftyear);
}
void build(int index,int Left,int Right,const int* a,const int* b) {
if(Left==Right) {
tree[index]=Tree(a[Left],a[Left],b[Left],1);
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a,b);
build(rs,mid+1,Right,a,b);
push_up(index);
}
int query_max(int index,int Left,int Right) {
if(Right<tree[index].leftyear||Left>tree[index].rightyear)return 0;
if(Left<=tree[index].leftyear&&Right>=tree[index].rightyear)return tree[index].max;
return max(query_max(ls,Left,Right),query_max(rs,Left,Right));
}
bool query_known(int index,int Left,int Right) {
if(Right<tree[index].leftyear||Left>tree[index].rightyear)return 1;
if(Left<=tree[index].leftyear&&Right>=tree[index].rightyear)return tree[index].known;
return query_known(ls,Left,Right)&&query_known(rs,Left,Right)&&(tree[ls].rightyear<Left||tree[rs].leftyear>Right||tree[ls].rightyear+1==tree[rs].leftyear);
}
} st;
int n,m,a[maxn],b[maxn];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int(),b[i]=Get_Int();
st.build(1,1,n,a,b);
m=Get_Int();
for(int i=1; i<=m; i++) {
int left=Get_Int(),right=Get_Int();
int l=st.query_max(1,left,left),r=st.query_max(1,right,right);
if(right<=left)puts("false");
else if(!l&&!r)puts("maybe");
else {
int tmp1=upper_bound(a+1,a+n+1,left)-a,tmp2=lower_bound(a+1,a+n+1,right)-a-1,l1,r1;
if(tmp1>n)l1=0x7fffffff/2;
else l1=a[tmp1];
if(tmp2<1)r1=-0x7fffffff/2;
else r1=a[tmp2];
if(!l) { //左边未知
if(l1>r1||r1==-0x7fffffff/2) {
puts("maybe");
continue;
}
int ans=st.query_max(1,l1,r1);
if(ans>=r)puts("false");
else puts("maybe");
} else if(!r) { //右边未知
if(l1>r1||l1==0x7fffffff/2) {
puts("maybe");
continue;
}
int ans=st.query_max(1,l1,r1);
if(ans>=l)puts("false");
else puts("maybe");
} else {
if(r>l) {
puts("false");
continue;
}
if(l1>r1) {
if(left+1==right)puts("true");
else puts("maybe");
continue;
}
int ans=st.query_max(1,l1,r1),known=st.query_known(1,l1,r1);
if(ans>=r)puts("false");
else if(!known||left+1!=l1||right-1!=r1)puts("maybe");
else puts("true");
}
}
}
return 0;
}
姥爷们赏瓶冰阔落吧~