【bzoj1067】[SCOI2007]降雨量 (RMQ)

Description

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

Input

输入仅一行包含一个正整数n,为已知的数据。以下n行每行两个整数yi和ri,为年份和降雨量,按照年份从小到大排列,即yi<yi+1。下一行包含一个正整数m,为询问的次数。以下m行每行包含两个数Y和X,即询问“X年是自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

对于每一个询问,输出true,false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

题解:

这题题意很简单,但需要分类的情况不少,细节还容易写错,我就不吐槽自己思路正确情况下找bug对拍了半小时…..
询问y,x.
首先,true情况最明显只有一种:x与y的值都已知,且y值小于x值,且x+1到y-1都已知,并且都小于x值.
然后就是 maybe的情况有三种:

  • 1.Y年和X年的降雨量已知,X年的降雨量不超过Y年的降雨量,从Y+1到X-1年中存在至少一年的降雨量未知,从Y+1到X-1年中已知的降雨量都小于X年的降雨量。
  • 2.Y年和X年中有且仅有一年的降雨量未知,从Y+1到X-1年中已知的降雨量都小于X年的降雨量。
  • 3.Y年和X年的降雨量都未知。
    以上三组条件中只要满足任意一组,答案即为”maybe”。

其他情况都是‘false’
我用RMQ实现找区间的极值,以及二分找没有出现点的范围。写的时候,注意一下细节,Y=X+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
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf=0x373737;
map<int,int>dy;
map<int,int>dd;
int A[100000+10],dmax[100000+10][25],n,cnt[100000+10];
void RMQ_init(){//数组下标从0开始
for(int i=0;i<n;i++) dmax[i][0]=dy[A[i]];
for(int j=1;(1<<j)<=n;j++){
for(int i=0;i+(1<<j)-1<n;i++){
//dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);
dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
}
}
}
int rmq(int l,int r){//ok=0返回最小值,ok=1返回最大值
if(l==r) return dmax[l][0];
int k=0;
while((1<<(k+1))<=r-l+1) k++;
return max(dmax[l][k],dmax[r-(1<<k)+1][k]);
}
int main(){
#ifdef yxj
freopen("C:\\Users\\MrYx\\Desktop\\a.txt","r",stdin);
freopen("C:\\Users\\MrYx\\Desktop\\c.txt","w",stdout);
#endif // yxj
while(~scanf("%d",&n)){
int t=0;dy.clear();dd.clear();
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++){
int a,b;scanf("%d%d",&a,&b);
dd[a]=t;
A[t++]=a;
dy[a]=b;
}
RMQ_init();
int m;scanf("%d",&m);
while(m--){
int x,y;scanf("%d%d",&y,&x);
/*
if(x<y){
printf("false\n");
continue;
}
*/
int maxx;
if(dd.count(x)&&dd.count(y)) maxx=rmq(dd[y]+1,dd[x]-1);
if(dd.count(x)&&dd.count(y)){
if(dy[y]>=dy[x]&&(maxx<dy[x]||dd[x]-dd[y]==1)){
if(x-y==dd[x]-dd[y]) printf("true\n");
else printf("maybe\n");
}
else printf("false\n");
}
else if(dd.count(x)||dd.count(y)){
if(dd.count(x)){
int p=lower_bound(A,A+n,y)-A;
//cout<<"pp="<<p<<endl;
int maxx=rmq(p,dd[x]-1);
//cout<<"maxxx="<<maxx<<endl;
if(p==dd[x]||maxx<dy[x]) printf("maybe\n");
else printf("false\n");
}
else{
int p=lower_bound(A,A+n,x)-A;
//cout<<"p="<<p<<endl;
int maxx=rmq(dd[y]+1,p-1);
//cout<<"maxx"<<maxx<<endl;
if(dd[y]==p-1||maxx<dy[y]) printf("maybe\n");
else printf("false\n");
}
}
else{
printf("maybe\n");
}
}
}
}
扫码也许会变得更强~!