简单说
拿map映射了年份
如果中间有空的年份就在映射里也跳过
st表记录区间最大和最小值
判断有跳过的最小值就是0
by Honahec @ 2022-08-03 10:26:43
st表应该是对的？
应该是后面的判断部分出了什么问题？
by Honahec @ 2022-08-03 10:27:57
AC代码
```
#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;
}
by WANG_ZHENG_MING @ 2022-08-03 10:37:53
@[Honahec](/user/306226) AC代码
by WANG_ZHENG_MING @ 2022-08-03 10:38:39
已 AC 感谢
在X年份未知的判断下出现了错误
by Honahec @ 2022-08-03 10:56:46