前言：看到这个题目的时候分析了一下，就是最大值问题，但是要注意分类讨论

以后遇到离散化的问题，还可以开一个map来记录存在的点，免得二分查找的点不存在

---

#include<bits/stdc++.h>
using namespace std;const int N = (int)5e4 + 5;
int ti[N], rain[N];
int n, m;
int back, top = -1;
int b[N];
int c[N];
int ans[N];
int big[N];
vector<int> v;int record[N];int getid(int t) {return lower_bound(v.begin(), v.end(), t) - v.begin() + 1;
}map<int, int> mp;void fun1() {// 维护一个前面都比自己高的滑动窗口
//cout << getid(-110) << endl;for (int i = n; i; i--) {int u = rain[i];while (back <= top) {int pos = b[top];if (rain[pos] <= u) {ans[pos] = ti[i]; top--;}else break;}b[++top] = i;}while (back <= top) {int pos = b[top];ans[pos] = ti[1] - 1;top--;}
}void fun2() {back = 0, top = -1;for (int i = 1; i <= n; i++) {int u = rain[i];while (back <= top) {int pos = c[top];if (rain[pos] <= u) {big[pos] = ti[i]; top--;}else break;}c[++top] = i;}while (back <= top) {int pos = c[top];big[pos] = ti[n] + 1;top--;}
}int main() {cin >> n;int ma = 0;for (int i = 1; i <= n; i++) {cin >> ti[i] >> rain[i];v.push_back(ti[i]);if (ti[i] != ti[i - 1] + 1) {record[i] = record[i - 1] + 1;}else record[i] = record[i - 1];mp[ti[i]] = 1;}fun1();fun2();//for (int i = 1; i <= n; i++) {//	cout << " i " << ans[i] << " " << big[i] << endl;//	cout << record[i] << endl;//}cin >> m;for (int i = 1; i <= m; i++) {int l, r; cin >> l >> r;int idr = getid(r), idl = getid(l);if (mp[l] && mp[r]) {if (ans[idr] == l) {if (record[idr] - record[idl]) {cout << "maybe" << endl;}else cout << "true" << endl;}else cout << "false" << endl;}else if (mp[r]) {int v = ans[idr];if (v > l && mp[v]) {cout << "false" << endl;}else cout << "maybe" << endl;}else if (mp[l]) {int v = big[idl];//cout << " v " << v << endl;if (v < r && mp[v]) {cout << "false" << endl;}else cout << "maybe" << endl;}else cout << "maybe" << endl;}return 0;
}