【BZOJ1067】【SCOI2007】降雨量

60 阅读 0 评论 40 点赞

我是靠谱客的博主幸福音响，最近开发中收集的这篇文章主要介绍【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 }