题目链接：
来了来了，BZOJ著名题目
(Juruo)少有的(1A)
很明显的一个分类讨论题，分以下(5)中情况来讨论。
设(l,r)为询问的两个年份，(Rain_i)表示(i)年的雨量。
-
(1.)答案为(true)
-
(Rain_lsim Rain_r)已知
-
(Rain_r<Rain_l)
-
(Rain_r>max{Rain_{l+1}sim Rain_{r-1}})
-
-
(2.)答案为(false)的一种：(Rain_l,Rain_r)已知
- (Rain_rge Rain_l)或(Rain_rlemax{Rain_{l+1}sim Rain_{r-1}})
-
(3.)答案为(false)的一种：(Rain_l)已知
- (Rain_l-max{Rain_{l+1}sim Rain_{r-1}}le 2)(没有足够的空隙留给(Rain_r))
-
(4.)答案为(false)的一种：(Rain_r)已知
- (Rain_rle max{Rain_{l+1}sim Rain_{r-1}})
- (5.)其他情况均为(maybe)
真简单
关于(max)查询我用的(ST)表，好写，常数小。
#include <cstdio>
#include <algorithm>
int n,m;
int Year[50005],Rain[50005];
int Log[50005],f[50005][17];
inline int Max(int l,int r)
{
if(l>r)return -1;
int k=Log[r-l+1];
return std::max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&Year[i],&Rain[i]);
for(int i=1;i<=n;++i)f[i][0]=Rain[i];
for(int i=2;i<=n;++i)Log[i]=Log[i>>1]+1;//预处理Log
for(int k=1;(1<<k)<=n;++k)
for(int i=1;i+(1<<k)-1<=n;++i)
f[i][k]=std::max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
scanf("%d",&m);
for(int l,r;m--;)
{
scanf("%d%d",&l,&r);
int p1=std::lower_bound(Year+1,Year+n+1,l)-Year;
int p2=std::lower_bound(Year+1,Year+n+1,r)-Year;
if(Year[p1]==l&&Year[p2]==r&&p2-p1==r-l&&Rain[p2]<Rain[p1]&&Rain[p2]>Max(p1+1,p2-1))
puts("true");
else if(Year[p1]==l&&Year[p2]==r&&(Rain[p2]>=Rain[p1]||Rain[p2]<=Max(p1+1,p2-1)))
puts("false");
else if(Year[p1]==l&&Year[p2]!=r&&Rain[p1]-Max(p1+1,p2-1)<2)
puts("false");
else if(Year[p1]!=l&&Year[p2]==r&&Rain[p2]<=Max(p1,p2-1))
puts("false");
else
puts("maybe");
}
return 0;
}
(Upadte:)似乎很多人没有考虑第(3)种情况？