BZOJ 1067 【SCOI2007】 降雨量
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1067
【题意】
给定一些年份和当年的降雨量，判定“X年是自Y年以来降水量最大的一年”这句话是真的，假的还是可能的。
【题解】
RMQ之后分类讨论。
WA得连北是哪边都不认识了
【代码】
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,f[50100][50];
int a[50100],b[50100];
int get_max(int x,int y)
{
if (x>y) return -1;
int l=(int) log2(y-x+1);
return max(f[x][l],f[y-(1<<l)+1][l]);
}
int main()
{
int n,M,i,j,x,y,p,q,temp;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
f[i][0]=b[i];
}
M=(int) log2(n);
for (j=1;j<=M;j++)
for (i=1;i<=n-(1<<j)+1;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
scanf("%d",&m);
while (m--)
{
scanf("%d%d",&x,&y);
if (y<x)
{
printf("false\n");
continue;
}
p=lower_bound(a+1,a+1+n,x)-a;
q=lower_bound(a+1,a+1+n,y)-a;
if (a[p]!=x && a[q]!=y)
{
printf("maybe\n");
continue;
}
if (a[p]!=x)
{
temp=get_max(p,q-1);
if (b[q]>temp)
printf("maybe\n");
else
printf("false\n");
continue;
}
if (a[q]!=y)
{
temp=get_max(p+1,q-1);
if (b[p]>temp)
printf("maybe\n");
else
printf("false\n");
continue;
}
if (b[p]<b[q])
{
printf("false\n");
continue;
}
if (y-x+1==q-p+1)
{
temp=get_max(p+1,q-1);
if (temp<b[q] && b[q]<=b[p])
printf("true\n");
else
printf("false\n");
continue;
}
else
{
temp=get_max(p+1,q-1);
if (temp<b[q] && b[q]<=b[p])
printf("maybe\n");
else
printf ("false\n");
}
}
return 0;
}