首先我们来分析一下题意。
题目会给出两个大小为 \(n\) 的数组，\(y\) 和 \(r\) ，其中 \(y_i\) 表示第 \(i\) 个年份是第几年，\(r_i\) 表示的是第 \(y_i\) 年的降雨量。之后，将会有 \(m\) 次询问，每次询问给出两个年份 \(Y\) 和 \(X\) ，若用 Z 表示 \(Y\) 和 \(X\) 之间的年份，则我们要判断的是三个年份的降雨量是否满足 \(Y\geqslant X>Z\) ，根据判断结果输出不同的话。
很显然，这是一个 \(RMQ\) 问题， \(RMQ\) 问题有多种方式解决，下面将只给出 \(ST\)表的解法。(其实我不会线段树，单调栈也忘记怎么写了)
这道题看似是一道水题，其实它有非常多的坑点，因为题目中的 \(Y,X,Z\) 之间会有很多种大小关系，而对于每一种关系，我们都要判断输出的结果是 \(true\) ，\(false\) ，还是 \(maybe\) ，这就使得这道题会让人变得非常头疼。
对于 \(Y,X,Z\) 三者之间大小关系的分析，将直接在代码中给出。
然而，我们并不是只需判断 \(Y,X,Z\) 之间的关系，在某些情况下，我们还需判断 \(Y,X\) 之间所有年份的降水量是否已知。为了防止超时爆零，我们不能直接用 \(for\) 循环枚举判断，但是我们可以利用二分法查找中间年份，这样就不会超时。
因为这题的数据范围特别大， \(y_i\) 在 \(\pm 10^9\) 之间，我们不可能定义一个大小有 \(2*10^9\) 的数组来存储每一年的降水量，所以我们需要对所给的年份进行离散化处理。但是，题目中所给出的年份本来就是从小到大排列的，这就帮我们省去了离散化的步骤（即给出的已经处于离散化状态），我们只要直接按照所给顺序做就行。
代码如下：
#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long ll;
const int N=50005;
int a[N],b[N],d[N][20],lg[N]= {-1};
int n,m;
int query(int x) {
return lower_bound(a+1,a+1+n,x)-a;
}
void RMQ_init(int n) {
for (int i=1; i<=n; i++) {
d[i][0]=b[i];
lg[i]=lg[i/2]+1;
}
for (int j=1; 1<<j<=n; j++) {
for (int i=1; i+(1<<j)-1<=n; i++) {
d[i][j]=max(d[i][j-1],d[i+(1<<j-1)][j-1]);
}
}
}
int RMQ(int l,int r) {
if (l>r) return -1;
int k=lg[r-l+1];
return max(d[l][k],d[r-(1<<k)+1][k]);
}
int main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%lld %lld",&a[i],&b[i]);
RMQ_init(n);
scanf("%d",&m);
for (int _=1; _<=m; _++) {
ll o,p;
scanf("%lld %lld",&o,&p);
int x=query(p),y=query(o);
int rmq=RMQ(y+1,x-1);
if (y>x) {
puts("false");
} else {
if (x<=n && a[x]==p) {
//x年份存在
if (y<=n && a[y]==o) {
//y年份存在
bool now=1;
if (rmq==-1) {
//x,y中间无已知年份时
if (b[x]<=b[y]) { //x的降雨量小于等于y
if (p-o==x-y) puts("true"); //x，y为连续的两年
else puts("maybe");//x，y中间有其他年份
} else {
puts("false");//x的降雨量大于y
}
now=0;
}
if (!now) goto M;
if (b[y]<b[x] || b[x]<=rmq) {
//y年降雨量比x年小或者x~y之间有一年的降雨量大于x年
puts("false");
} else {
//b[y]>b[x]>rmq
if (x-y!=p-o) {
//第i年的降雨量未知
puts("maybe");
} else puts("true"); //中间年份全部存在
}
} else {
//y年不存在
if (RMQ(y,x-1)>=b[x]) {
//ps:此时，第一个降雨量大于等于p的年份，
// 也就是中间年份的第一项就是y。
//中间年份存在降雨量大于等于x年的一年
puts("false");
} else {
//y年不存在，无论中间年份降雨量如何，结果都是未知的
puts("maybe");
}
}
} else {
//x年不存在
if (y<=n && a[y]==o) {
//y年存在
if (rmq>=b[y]) puts("false"); //rmq>=a[y]时
else puts("maybe");//a[y]>rmq时，x年未知
} else puts("maybe");//x，y都未知时。
}
}
M:;
}
return 0;
}
祝各位大佬早日 \(AKIOI\) 。
原文：https://www.cnblogs.com/you-mu-jv-ruo/p/13226387.html