【BZOJ1067】【SCOI2007】降雨量

124 阅读 0 评论 82 点赞

我是靠谱客的博主幸福音响，这篇文章主要介绍【BZOJ1067】【SCOI2007】降雨量，现在分享给大家，希望可以做个参考。

新人求助，降雨量那题，本机AC提交AC

原题：

我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，
则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知，有的说法是可能正确也可以不正确的。

1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

（不算太神的）神题，经过3h的静态查错+对拍终于1A，好感动QAQ

其实这题思路是很简单的，时限也卡得不严，但是需要讨论的情况比较多而且很容易被忽略，考验思维精细程度

做法就是直接上线段树，每次根据某个位置或某段区间的值和某个位置或某段区间中有没有没有被钦定值来判断答案

判断某个位置或某段区间有没有被钦定可以直接取最小值（数据保证降雨量>=1）或01标记求区间和/区间最大值

然后就是情况大讨论辣！

具体都有什么情况就不说了，请同学们自行思考来锻炼思维精细程度

（其实是我实在不想再把各种情况讨论一遍了

如果实在WA不过去可以参考一下AC代码……

代码：

复制代码

1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 const int oo=168430090;
 8 int rd(){int z=0,mk=1;
char ch=getchar();
 9
while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;
ch=getchar();}
10
while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';
ch=getchar();}
11
return z*mk;
12 }
13 int n,m,a[121000],b[121000];
int N,M;
14 int c[241000],tt=0;
15 int e[2][481000];
16 int bnrsch(int x){
17
int l=1,r=tt,md;
18
while(l+1<r){
md=(l+r)>>1;
(x<=c[md] ? r : l)=md;}
19
return c[l]==x ? l : r;
20 }
21 void mdf(int y,int z,int mk){
22
int x=1,l=1,r=tt,md;
23
for(;;){
24
e[mk][x]=max(e[mk][x],z);
25
if(l==r)
break;
26
md=(l+r)>>1;
27
if(y<=md)
r=md,x<<=1;
28
else
l=md+1,x=x<<1|1;
29 
}
30 }
31 int sch(int x,int l,int r,int ll,int rr,int mk){
32
if(l<ll || r>rr || l>r)
return 0;
33
if(l==ll && r==rr)
return e[mk][x];
34
int md=(ll+rr)>>1;
35
if(l<=md && r>md)
return max(sch(x<<1,l,md,ll,md,mk),sch(x<<1|1,md+1,r,md+1,rr,mk));
36
else if(r<=md)
return sch(x<<1,l,r,ll,md,mk);
37
else
return sch(x<<1|1,l,r,md+1,rr,mk);
38 }
39 int main(){//freopen("ddd.in","r",stdin);
40
//freopen("ddd.out","w",stdout);
41
memset(e,0,sizeof(e));
42
cin>>n;
N=n<<1|1;
43
for(int i=1;i<=n;++i)
a[i<<1]=rd(),a[i<<1|1]=rd();
44
cin>>m;
M=m<<1|1;
45
for(int i=1;i<=m;++i)
a[N+(i<<1)]=rd(),a[N+(i<<1|1)]=rd();
46
for(int i=1;i<=N+M;++i)
b[i]=a[i];
47
sort(b+1,b+N+M+1);
48
b[0]=-oo;
49
for(int i=1;i<=N+M;++i)if(b[i]!=b[i-1]){
50
if(b[i]-1!=b[i-1])
c[++tt]=b[i]-1;
51
c[++tt]=b[i];
52 
}
53
int l,r,lst=0,z,y;
54
for(int i=1;i<=n;++i){
55
l=bnrsch(a[i<<1]),r=a[i<<1|1];
56
for(int i=lst+1;i<l;++i)
mdf(i,1,1);
57
lst=l;
58
mdf(l,r,0);
59 
}
60
for(int i=1;i<=m;++i){
61
l=bnrsch(a[N+(i<<1)]),r=bnrsch(a[N+(i<<1|1)]);
62
if(l==r){
printf("truen");
continue; }
63
z=sch(1,r,r,1,tt,0),y=sch(1,l,l,1,tt,0);
64
//if(!(z<=sch(1,l,l,1,tt,0) && z>sch(1,l+1,r-1,1,tt,0)))
printf("falsen");
65
/*if(sch(1,l+1,r-1,1,tt,0)>=y)
printf("falsen");
66 
else if(sch(1,r,r,1,tt,1))
printf("mayben");
67 
else if(z>sch(1,l+1,r-1,1,tt,0) && (sch(1,l,l,1,tt,1) || z<=y){
68 
if(y<z)
printf("falsen");
69 
if(sch(1,l,r,1,tt,1))
printf("mayben");
70 
else
printf("truen");
71 
}*/
72
if(y && sch(1,l+1,r-1,1,tt,0)>=y)
printf("falsen");
73
else if(!z)
printf("mayben");
74
else if(z>sch(1,l+1,r-1,1,tt,0) && (!y || z<=y)){
75
if(sch(1,l,r,1,tt,1))
printf("mayben");
76
else
printf("truen");
77 
}
78
else
printf("falsen");
79 
}
80
return 0;
81 }

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
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 const int oo=168430090;
 8 int rd(){int z=0,mk=1;
char ch=getchar();
 9
while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;
ch=getchar();}
10
while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';
ch=getchar();}
11
return z*mk;
12 }
13 int n,m,a[121000],b[121000];
int N,M;
14 int c[241000],tt=0;
15 int e[2][481000];
16 int bnrsch(int x){
17
int l=1,r=tt,md;
18
while(l+1<r){
md=(l+r)>>1;
(x<=c[md] ? r : l)=md;}
19
return c[l]==x ? l : r;
20 }
21 void mdf(int y,int z,int mk){
22
int x=1,l=1,r=tt,md;
23
for(;;){
24
e[mk][x]=max(e[mk][x],z);
25
if(l==r)
break;
26
md=(l+r)>>1;
27
if(y<=md)
r=md,x<<=1;
28
else
l=md+1,x=x<<1|1;
29 
}
30 }
31 int sch(int x,int l,int r,int ll,int rr,int mk){
32
if(l<ll || r>rr || l>r)
return 0;
33
if(l==ll && r==rr)
return e[mk][x];
34
int md=(ll+rr)>>1;
35
if(l<=md && r>md)
return max(sch(x<<1,l,md,ll,md,mk),sch(x<<1|1,md+1,r,md+1,rr,mk));
36
else if(r<=md)
return sch(x<<1,l,r,ll,md,mk);
37
else
return sch(x<<1|1,l,r,md+1,rr,mk);
38 }
39 int main(){//freopen("ddd.in","r",stdin);
40
//freopen("ddd.out","w",stdout);
41
memset(e,0,sizeof(e));
42
cin>>n;
N=n<<1|1;
43
for(int i=1;i<=n;++i)
a[i<<1]=rd(),a[i<<1|1]=rd();
44
cin>>m;
M=m<<1|1;
45
for(int i=1;i<=m;++i)
a[N+(i<<1)]=rd(),a[N+(i<<1|1)]=rd();
46
for(int i=1;i<=N+M;++i)
b[i]=a[i];
47
sort(b+1,b+N+M+1);
48
b[0]=-oo;
49
for(int i=1;i<=N+M;++i)if(b[i]!=b[i-1]){
50
if(b[i]-1!=b[i-1])
c[++tt]=b[i]-1;
51
c[++tt]=b[i];
52 
}
53
int l,r,lst=0,z,y;
54
for(int i=1;i<=n;++i){
55
l=bnrsch(a[i<<1]),r=a[i<<1|1];
56
for(int i=lst+1;i<l;++i)
mdf(i,1,1);
57
lst=l;
58
mdf(l,r,0);
59 
}
60
for(int i=1;i<=m;++i){
61
l=bnrsch(a[N+(i<<1)]),r=bnrsch(a[N+(i<<1|1)]);
62
if(l==r){
printf("truen");
continue; }
63
z=sch(1,r,r,1,tt,0),y=sch(1,l,l,1,tt,0);
64
//if(!(z<=sch(1,l,l,1,tt,0) && z>sch(1,l+1,r-1,1,tt,0)))
printf("falsen");
65
/*if(sch(1,l+1,r-1,1,tt,0)>=y)
printf("falsen");
66 
else if(sch(1,r,r,1,tt,1))
printf("mayben");
67 
else if(z>sch(1,l+1,r-1,1,tt,0) && (sch(1,l,l,1,tt,1) || z<=y){
68 
if(y<z)
printf("falsen");
69 
if(sch(1,l,r,1,tt,1))
printf("mayben");
70 
else
printf("truen");
71 
}*/
72
if(y && sch(1,l+1,r-1,1,tt,0)>=y)
printf("falsen");
73
else if(!z)
printf("mayben");
74
else if(z>sch(1,l+1,r-1,1,tt,0) && (!y || z<=y)){
75
if(sch(1,l,r,1,tt,1))
printf("mayben");
76
else
printf("truen");
77 
}
78
else
printf("falsen");
79 
}
80
return 0;
81 }