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
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
数据范围及提示 Data Size & Hint
100%的数据满足：1<=n<=50000, 1<=m<=10000, -109<=yi<=109, 1<=ri<=109
题解：
ST表维护区间+二分查找
代码：
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
#define maxn 100005
#define LOGN 18 using namespace std; int n,st[LOGN][maxn],q,x,y,d[maxn],a[maxn],ans,logn,Log[maxn]; int query(int l, int r)
{
if (l>r) return INT_MIN;
int len=Log[r-l+];
return max(st[len][l],st[len][r-(<<len)+]);
} void build()
{
logn=Log[n];
for (int i=; i<=n;i++) st[][i]=a[i];
for (int i=; i<=logn;i++)
for (int j=;j<=n-(<<i)+;j++)
st[i][j]=max(st[i-][j],st[i-][j+(<<i-)]);
} int getpos(int x){ return lower_bound(d + , d + n + , x) - d; } int main()
{
for (int i=,j=,k=-;i<=maxn;i++)
if (i==j) Log[i]=++k,j<<=;
else Log[i]=k;
scanf("%d",&n);
for (int i=;i<=n;++i)
scanf("%d%d",d+i,a+i);
scanf("%d",&q);
build();
while (q--)
{
scanf("%d%d",&x,&y);
int l=getpos(x),r=getpos(y),m;
bool lx=l<=n&&d[l]==x,rx=r<=n&&d[r]==y;
if (!rx) --r;
if (lx)
if (rx)
{
m = query(l+, r-);
if (a[l]<a[r]) ans=;
else
if (m<a[r])
if (r-l==y-x) ans=;
else ans=-;
else ans=;
}
else
{
m=query(l+,r);
if (m<a[l]) ans=-;
else ans=;
}
else
if (rx)
{
m=query(l,r-);
if (m < a[r]) ans=-;
else ans = ;
}
else ans=-;
if (ans==) printf("true\n");
else if (!ans) printf("false\n");
else printf("maybe\n");
}
return ;
}