## 链接：

https://www.lucien.ink/go/P2471/

## 题目：

### 样例输入

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

### 样例输出

false
true
false
maybe
false

### 提示

100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

## 思路：

首先把年份离散化一下，建立一个维护最大值的线段树，根据题目所给的条件判一判就可以了。

## 实现：

#include <cstdio>
#include <map>
#include <algorithm>
#define lson t << 1
#define rson t << 1 | 1
const int maxn = 50007;
int max[maxn << 2], num[maxn], year[maxn], n, m;
std::map<int, int> index;
void pushup(int t) { max[t] = std::max(max[lson], max[rson]); }
void build(int t = 1, int l = 1, int r = n) {
if (l == r) {
max[t] = num[l];
return ;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(t);
}
int query(int begin, int end, int t = 1, int l = 1, int r = n) { // 查询区间最大值
if (begin > end) return -1;
if (begin <= l && r <= end) return max[t];
int mid = l + r >> 1;
if (begin > mid) return query(begin, end, rson, mid + 1, r);
if (end <= mid) return query(begin, end, lson, l, mid);
return std::max(query(begin, end, rson, mid + 1, r), query(begin, end, lson, l, mid));
}
int judge(int y, int x) {
int l = int(std::upper_bound(year + 1, year + 1 + n, y) - year);
int r = int(std::lower_bound(year + 1, year + 1 + n, x) - year) - 1;
int maxnum = query(l, r), num_y = num[index[y]], num_x = num[index[x]];
if (num_x && maxnum >= num_x) return 0; // (y, x)里的左右年降雨量都要严格小于x和y
if (num_y && maxnum >= num_y) return 0;
if (num_y && num_y < num_x) return 0; // x年的降雨量不能超过y年
if (num_y == 0 || num_x == 0) return -1;
if (r - l + 2 != x - y) return -1; // 如果x和y之间的区间长度和离散化后的区间长度不同，说明有未知年份
return 1;

}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", year + i, num + i); // num代表降雨量
index[year[i]] = i; // 离散化
}
build();
scanf("%d", &m);
for (int i = 0, y, x; i < m; i++) {
scanf("%d%d", &y, &x);
switch (judge(y, x)) {
case -1: puts("maybe"); break;
case 0: puts("false"); break;
case 1: puts("true"); break;
default: break;
}
}
return 0;
}
Responses
1. Dav

if (num_y == 0 || num_x == 0) return -1;
请问这一行是为什么？