BZOJ1067: [SCOI2007]降雨量

1067: [SCOI2007]降雨量

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1944 Solved: 489
[Submit][Status]

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

Source

POJ 2637 WorstWeather Ever

题解：

一眼想到了单调栈，然后敲完之后一边过样例，交上去WA，才发现这题细节好多，比如会出现没有描述的年份，然后lower__bound和upper__boung又会出现各种各样的问题。。。

看了一眼网上的题解都说要RMQ？我觉得单调栈可过啊，于是继续yy，终于yy出来了。。。

    int top=0;
    b[0]=inf;
    for(int i=n;i>=0;i--)
    {
        while(top>0&&b[i]>=b[sta[top]])l[sta[top--]]=i;
        sta[++top]=i;
    }
    top=0;
    b[n+1]=inf;
    for(int i=1;i<=n+1;i++)
    {
        while(top>0&&b[i]>=b[sta[top]])r[sta[top--]]=i;
        sta[++top]=i;
    }

首先，这一步用单调栈求出每一个点作为最大降雨量向左向右各能拓展到哪里。

int x=read(),y=read();
        cit xx=c.lower_bound(x),yy=--c.upper_bound(y);
        int xxx=xx->second,yyy=yy->second;
        //cout<<x<<' '<<y<<' '<<xxx<<' '<<yyy<<endl;
        if(a[xxx]==x&&a[yyy]==y)
        {
          if(l[yyy]!=xxx)puts("false");
          else if(yyy-xxx!=y-x)puts("maybe");
          else puts("true");
        }
        else if(a[xxx]==x)
        {
          if(r[xxx]<=yyy)puts("false");
          else puts("maybe");    
        }
        else if(a[yyy]==y)
        {
          if(l[yyy]>=xxx)puts("false");
          else puts("maybe");
        }
        else puts("maybe");

这里是程序的关键，我用了一个map 实现年份到数组下标的映射，当然也可以记录成数组二分查找。下面考虑几种情况：

（xxx表示年份>=x的第一个下标，yyy表示年份<=y的第一个下标）

1.x y 的降雨量都已知

那么如果 l[yyy]!=xxx说明要么 y作为最大值拓展不到 x，要么 y的降雨量>降雨量都不满足题意直接输出 false 即可

否则若 yyy-xxx=y-x 说明这中间至少存在一年的降雨量未知，所以我们输出 maybe

否则输出 true

2.x 的降雨量已知

那么我们要看 r[xxx]<=yyy，即x的降雨量作为最大值能否拓展过yyy，不能则说明在这之中有一个月份的降雨量>=x的降雨量，输出false

否则输出maybe

3.y 的降雨量已知

那么我们类似的看 l[yyy]>=xxx，即y的降雨量作为最大值能否拓展过xxx，不能输出false

否则输出maybe

4.x y 都不知道

直接输出maybe

有一点要注意的

lower _bound >= upper_bound >

--lower_bound < --upper_bound <=

代码：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #define inf 1000000000
12 #define maxn 50000+1000
13 #define maxm 500+100
14 #define eps 1e-10
15 #define ll long long
16 #define pa pair<int,int>
17 using namespace std;
18 typedef map<int,int>::const_iterator cit;
19 typedef map<int,int>::value_type vt;
20 map<int,int>c;
21 int n,m,sta[maxn],a[maxn],b[maxn],l[maxn],r[maxn];
22 inline int read()
23 {
24     int x=0,f=1;char ch=getchar();
25     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
26     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
27     return x*f;
28 }
29 int main()
30 {
31     freopen("input.txt","r",stdin);
32     freopen("output.txt","w",stdout);
33     n=read();
34     for(int i=1;i<=n;i++)
35      {
36       a[i]=read();b[i]=read();
37       c.insert(c.begin(),vt(a[i],i));
38      }  
39     int top=0;
40     b[0]=inf;
41     for(int i=n;i>=0;i--)
42     {
43         while(top>0&&b[i]>=b[sta[top]])l[sta[top--]]=i;
44         sta[++top]=i;
45     }
46     top=0;
47     b[n+1]=inf;
48     for(int i=1;i<=n+1;i++)
49     {
50         while(top>0&&b[i]>=b[sta[top]])r[sta[top--]]=i;
51         sta[++top]=i;
52     }
53     m=read();
54     while(m--)
55     {
56         int x=read(),y=read();
57         cit xx=c.lower_bound(x),yy=--c.upper_bound(y);
58         int xxx=xx->second,yyy=yy->second;
59         //cout<<x<<' '<<y<<' '<<xxx<<' '<<yyy<<endl;
60         if(a[xxx]==x&&a[yyy]==y)
61         {
62           if(l[yyy]!=xxx)puts("false");
63           else if(yyy-xxx!=y-x)puts("maybe");
64           else puts("true");
65         }
66         else if(a[xxx]==x)
67         {
68           if(r[xxx]<=yyy)puts("false");
69           else puts("maybe");    
70         }
71         else if(a[yyy]==y)
72         {
73           if(l[yyy]>=xxx)puts("false");
74           else puts("maybe");
75         }
76         else puts("maybe");
77     }
78     return 0;
79 }

View Code