Bakser's Blog

我是逗比。

bzoj1067 RMQ+特判

| Comments

此题算法比较简单,但对于各种情况的特判相当蛋疼
设询问为l,r
若l,r都未知 maybe
若l,r都已知
1.r降雨量大于l或(l,r)中有大于r的-----false
2.满足条件且(l,r)都已知-----true
3.满足条件且(l,r)有未知的----maybe
若l已知
(l,r)中有大于l的---false
否则-----maybe
若r已知
(l,r)中有大于r的---false
否则-----maybe
其他都false

代码还是比较简洁的。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 50100
#define MAX(a,b) (((a)>(b))?(a):(b))
#define ans(x) {puts(x);continue;}
LL f[N][18],year[N],rain[N],l,r;
int unknown[N],n,m;
inline void Init_st()
{
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i+(1<<j)-1<n;i++)
    f[i][j]=MAX(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline LL query(int l,int r)
{
    if(l>r)return -0x3f3f3f3f3f3f3f3fLL;
    int k=(int)(log((double)(r-l+1))/log(2.0));
    return MAX(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",year+i,rain+i);
        f[i][0]=rain[i];
        unknown[i]=unknown[i-1]+year[i]-year[i-1]-1;
    }
    Init_st();
    scanf("%d",&m);
    while(m--)
    {
        scanf("%lld%lld",&l,&r);
        if(r<l)ans("false");
        if(l==r)ans("true");
        LL tl(l),tr(r);
        l=lower_bound(year+1,year+n+1,tl)-year;
        r=lower_bound(year+1,year+n+1,tr)-year;
        if((year[l]!=tl&&year[r]!=tr)||(tr<=year[1]||tl>=year[n]))ans("maybe");
        if(year[l]==tl&&year[r]==tr)
        {
            if(rain[r]>rain[l])ans("false");
            if(query(l+1,r-1)>=rain[r])ans("false");
            if(!(unknown[r]-unknown[l]))ans("true");
            ans("maybe");
        }
        if(year[l]==tl&&query(l+1,r-1)<rain[l])ans("maybe");
        if(year[r]==tr&&query(l,r-1)<rain[r])ans("maybe");
        ans("false");
    }
    return 0;
}

Comments

comments powered by Disqus