【bzoj1067】[SCOI2007]降雨量

2015.06.03 08:35 Wed | 23次阅读 | 旧日oi | 固定链接 | 源码

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

题解

思路很水,离散一下求个rmq搞一搞就行,但是细节超级多……
还好我有数据~
实在没什么好说的,直接放代码吧,还是很短滴~

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 50005
int n,q;
int y[N],r[N][17],num[N],lg[N];
void pre_RMQ()
{
    for(int j=1;j<=16;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            r[i][j]=max(r[i][j-1],r[i+(1<<(j-1))][j-1]);
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
}
int find(int x,int y)
{
    if(y<x) return 0;
    int t=lg[y-x+1];
    return max(r[x][t],r[y-(1<<t)+1][t]);
}
int main()
{
//  freopen("rain.in", "r", stdin);
//  freopen("rain.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&y[i],&r[i][0]);
        num[i]=y[i];
    }
    pre_RMQ();
    cin>>q;
    for(int a,b,i=1;i<=q;i++)
    {
        scanf("%d%d",&a,&b);
        if(a>=b)
        {
            puts("false");
            continue;
        }
        int t1=lower_bound(num+1,num+n+1,a)-num;
        int t2=lower_bound(num+1,num+n+1,b)-num;
        if(num[t1]==a&&num[t2]==b)
        {
            if(r[t1][0]<r[t2][0]) puts("false");
            else
            {
                int k=find(t1+1,t2-1);
                if(k>=r[t2][0]) puts("false");
                else if(b-a==t2-t1) puts("true");
                else puts("maybe");
            }
        }
        else if(num[t2]==b)
        {
            if(find(t1,t2-1)<r[t2][0]) puts("maybe");
            else puts("false");
        }
        else if(num[t1]==a)
        {
            if(find(t1+1,t2-1)<=r[t1][0]) puts("false");
            else puts("maybe");
        }
        else puts("maybe");
    }
}```