C++之路进阶——codevs2439（降雨量）

2439 降雨量

2007年省队选拔赛四川

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 大师 Master

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

2002 4920

2003 5901

2004 2832

2005 3890

2007 5609

2008 3024

2002 2005

2003 2005

2002 2007

2003 2007

2005 2008

样例输出 Sample Output

false

true

false

maybe

false

数据范围及提示 Data Size & Hint

100%的数据满足：1<=n<=50000, 1<=m<=10000, -109<=yi<=109, 1<=ri<=109

题解：

ST表维护区间+二分查找

代码：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <climits>
 4 #include <algorithm>
 5 #define maxn 100005
 6 #define LOGN 18
 7 
 8 using namespace std;
 9 
10 int n,st[LOGN][maxn],q,x,y,d[maxn],a[maxn],ans,logn,Log[maxn];
11 
12 int query(int l, int r)
13 {
14     if (l>r) return INT_MIN;
15     int len=Log[r-l+1];
16     return max(st[len][l],st[len][r-(1<<len)+1]);
17 }
18 
19 void build()
20 {
21     logn=Log[n];
22     for (int i=0; i<=n;i++) st[0][i]=a[i];
23     for (int i=1; i<=logn;i++)
24         for (int j=1;j<=n-(1<<i)+1;j++)
25             st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);    
26 }
27 
28 int getpos(int x){ return lower_bound(d + 1, d + n + 1, x) - d; }
29 
30 int main()
31 {
32     for (int i=1,j=1,k=-1;i<=maxn;i++)
33         if (i==j) Log[i]=++k,j<<=1;
34         else Log[i]=k;
35     scanf("%d",&n);
36     for (int i=1;i<=n;++i)
37         scanf("%d%d",d+i,a+i);
38     scanf("%d",&q);
39     build();
40     while (q--)
41     {
42         scanf("%d%d",&x,&y);
43         int l=getpos(x),r=getpos(y),m;
44         bool lx=l<=n&&d[l]==x,rx=r<=n&&d[r]==y;
45         if (!rx) --r;
46         if (lx)
47             if (rx)
48             {
49                 m = query(l+1, r-1);
50                 if (a[l]<a[r]) ans=0;
51                 else
52                     if (m<a[r])
53                         if (r-l==y-x) ans=1;
54                         else ans=-1;
55                     else ans=0;
56             }
57             else
58             {
59                 m=query(l+1,r);
60                 if (m<a[l]) ans=-1;
61                 else ans=0;
62             }
63         else
64             if (rx)
65             {
66                 m=query(l,r-1);
67                 if (m < a[r]) ans=-1;
68                 else ans = 0;
69             }
70             else ans=-1;
71         if (ans==1) printf("true
");
72         else if (!ans) printf("false
");
73         else printf("maybe
");
74     }
75     return 0;
76 }