链接
显然是用map映射一下，然后用线段树查询区间最值，如果给出的两年中有一年未知，二分找到它附近的位置（如果是x未知找第一个大于x的位置，如果是y未知找最大的小于y的位置）
然后再加亿点点细节：
我们就可以用这几个量来判断。
rain[i]：i位置的降雨量
year[i]：i位置的年份
x,y：题目中给定的年份
posx：当前x年的位置
posy：当前y年的位置
posz：(x, y)区间中最大雨量所在年份的位置
讨论主要分为四部分：
1.x，y都未知
2.x未知，y已知
3.x已知，y未知
4.x， y都已知
对于1情况：
maybe
对于2情况：
1.x是否等于y + 1
2.rain[posz] < rain[posy]还是rain[posz] >= rain[posy]
对于3情况：
1.x是否等于y + 1
2.rain[posz] < rain[posx]还是rain[posz] >= rain[posx]
对于4情况：
1.rain[posx] > rain[posy] false
2.x是否等于y + 1
3.x - y 是否等于posx - posy
4.rain[posz] < rain[posx]还是rain[posz] >= rain[posx]
其他细节：
1.如上文所说，lower_bound二分时posy要-1
2.求posz时注意posx和posy的关系，如果posx = posy + 1，一个-1一个+1时会报错
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
const int N = 50005;
struct node {
int r, y;//当前区间最大雨量和所在年份
} tree[N << 4];
int year[N], rain[N];
map<int, int> pos;
int n, m;
void update(int i) {
if(tree[i << 1].r >= tree[i << 1 | 1].r) {
tree[i].r = tree[i << 1].r, tree[i].y = tree[i << 1].y;
} else {
tree[i].r = tree[i << 1 | 1].r, tree[i].y = tree[i << 1 | 1].y;
}
}
void build(int i, int l, int r) {
if(l == r) {
tree[i].y = year[l], tree[i].r = rain[l];
return ;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
update(i);
}
node query(int i, int l, int r, int nl, int nr) {//求区间最值
if(l >= nl && r <= nr) return tree[i];
int mid = (l + r) >> 1;
if(nr <= mid) return query(i << 1, l, mid, nl, nr);
if(nl > mid) return query(i << 1 | 1, mid + 1, r, nl, nr);
node tmp1 = query(i << 1, l, mid, nl, nr);
node tmp2 = query(i << 1 | 1, mid + 1, r, nl, nr);
if(tmp1.r >= tmp2.r) return tmp1;
else return tmp2;
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &year[i], &rain[i]);
pos[year[i]] = i;
}
build(1, 1, n);
scanf("%d", &m);
for(int i = 1; i <= m; i++) {
int x, y; scanf("%d%d", &y, &x);
int posx = pos[x], posy = pos[y];
if(!posx && !posy) {//都未知
printf("maybe
"); continue;
}
if(!posx && posy) {//x未知y已知
posx = lower_bound(year + 1, year + 1 + n, x) - year;
if(x == y + 1) {
printf("maybe
"); continue;
}
int posz;
if(posx == posy + 1) posz = 0;
else posz = pos[query(1, 1, n, posy + 1, posx - 1).y];
if(rain[posz] < rain[posy]) {
printf("maybe
"); continue;
} else if(rain[posz] >= rain[posy]) {
printf("false
"); continue;
}
}
if(posx && !posy) {//x已知y未知
if(x == y + 1) {
printf("maybe
"); continue;
}
posy = lower_bound(year + 1, year + 1 + n, y) - year - 1;
int posz;
if(posx == posy + 1) posz = 0;
else posz = pos[query(1, 1, n, posy + 1, posx - 1).y];
if(rain[posz] < rain[posx]) {
printf("maybe
"); continue;
} else if(rain[posz] >= rain[posx]) {
printf("false
"); continue;
}
}//
if(posx && posy) {//都已知
if(rain[posx] > rain[posy]) {
printf("false
"); continue;
}
if(x == y + 1) {
if(x - y == posx - posy) {
printf("true
"); continue;
} else {
printf("maybe
"); continue;
}
} else if(x != y + 1) {
int posz;
if(posx == posy + 1) posz = 0;
else posz = pos[query(1, 1, n, posy + 1, posx - 1).y];
if(x - y == posx - posy) {
if(rain[posz] < rain[posx]) {
printf("true
"); continue;
} else {
printf("false
"); continue;
}
} else {
if(rain[posz] < rain[posx]) {
printf("maybe
"); continue;
} else {
printf("false
"); continue;
}
}
}
}
}
return 0;
}