题意：由小到大给出n年的降雨量，进行m次询问，每次询问给出一个Y和X，问X年的降雨量是否不超过Y，并且对于任意的Z∈(Y,X)的降雨量，是否都严格小于Y和X的降雨量
Solution
维护区间最大值很简单，但是要判断实在是太阴间了，这里来练习一下st表
st表
st表用于解决可重复贡献问题，基于倍增的思想，预处理：O(nlogn)，查询：O(1)，但是无法修改
预处理
令f[i] [j]表示区间[i,i+2j-1]的最大值，这样我们可以把这个区间对半撇成[i,i+2j-1-1]和[i+2j-1,i+2j-1]，以此类推
for(int j=1;j<=21;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]);
}
}
查询
对于每一个查询区间[l,r]，长度len=r-l+1，于是我们可以把他分为[l,l+2s-1]和[r-2s+1,r]，其中s=log(len)
void init() //预处理log
{
logn[1]=0;
logn[2]=1;
for(int i=3;i<N;i++)logn[i]=logn[i/2]+1;
}
题目
回到这到题来，区间最大值我们已经处理好了，接下来就是进行答案判断了
每次询问给出了Y和X，我们在输入的时候记录一下输入年份的下标，用map存一下，现在记下Y和X的下标为L和R
接下来是关于L和R的讨论
当L>0&&R>0时：
R-L=1的话，先判断大小是否正确，再判断X-Y是否等于1，即判断中间是否有未知的年份
R-L!=1的话，求出X,Y年份中间的降雨量最大值，进行比较，然后再根据R-L是否等于X-Y来判断有无未知年份
仅L>0时:
找到小于X年份的下标P，然后求出Y+1到P的降雨量最大值，然后判断是否合法
仅R>0时:
找到不小于Y年份的下标P，然后求出P到X-1的降雨量最大值，然后判断是否合法
注意这种情况和上一种都需要判断一下P有无与X或Y重合
L和R都不大于0：一定未知
void solve()
{
int n;scanf("%lld",&n);
map<int,int>mp;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&a[i],&f[i][0]);
mp[a[i]]=i;
}
init();
for(int j=1;j<=21;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]);
}
}
int m;scanf("%lld",&m);
while(m--)
{
int l,r;scanf("%lld%lld",&l,&r);
int x=mp[l],y=mp[r];
if(x>0&&y>0)
{
int s=logn[(y-1)-(x+1)+1];
int num=max(f[x+1][s],f[y-1-(1<<s)+1][s]);
if(y-x==1)
{
if(f[y][0]>f[x][0])cout<<"false\n";
else
{
if(r-l==1)cout<<"true\n";
else cout<<"maybe\n";
}
}
else if(num>=f[y][0]||num>=f[x][0]||f[y][0]>f[x][0])cout<<"false\n";
else
{
if(y-x+1==r-l+1)cout<<"true\n";
else cout<<"maybe\n";
}
}
else if(x>0)
{
int p=lower_bound(a+1,a+1+n,r)-a;
p--;
if(p==x)cout<<"maybe\n";
else
{
int s=logn[(p)-(x+1)+1];
int num=max(f[x+1][s],f[p-(1<<s)+1][s]);
if(num>=f[x][0])cout<<"false\n";
else cout<<"maybe\n";
}
}else if(y>0)
{
int p=lower_bound(a+1,a+1+n,l)-a;
if(p==y)cout<<"maybe\n";
else
{
int s=logn[(y-1)-(p)+1];
int num=max(f[p][s],f[y-1-(1<<s)+1][s]);
if(num>=f[y][0])cout<<"false\n";
else cout<<"maybe\n";
}
}else cout<<"maybe\n";
}
}