滑动窗口记录左右的最大值

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

以后遇到离散化的问题，还可以开一个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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112