问每次询问，Y与X，是否满足X是自Y以来最大降雨量的一年。
这题可以用ST表做。首先对年份进行离散化处理，数字相邻的离散化后的数字也相邻，但是中间有数字空白的，离散化时要差1位。
之后初始化st表，建立stmax和stmin两部分，某个区间的最小值为0，说明这个区间存在不确定的年份，这个是判maybe的一个关键条件。
之后只需要判断X与Y的关系，以及X与[Y+1, X-1]区间的最大值的关系。
注意：X需要小于等于Y，[Y+1, X-1]的每一个数也要满足这个条件，题干虽然没说但根据不等式也能推导出来
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1e5;
void solve();
void init();
int logn[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
int stmax[N][20],stmin[N][20];
void solve()
{
int n,m;
cin>>n;
int idx=1,last=0;
mpi h;
int x,y,r;
veci year;
for(int i=0;i<n;i++)
{
cin>>y>>r;
year.push_back(y);
if(i&&y-last>1)idx++;
last=y;
h[y]=idx++;
stmax[h[y]][0]=r;
}
n=idx;
for(int i=1;i<=n;i++)stmin[i][0]=stmax[i][0];
for(int j=1;j<20;j++)
{
for(int i=1;i<=n&&(i+(1<<(j-1)))<=n;i++)
{
stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
}
}
cin>>m;
while(m--)
{
cin>>y>>x;
if(y>=x)
{
cout<<"false"<<endl;
continue;
}
auto p = lower_bound(year.begin(),year.end(),x);
if(p==year.end())
{
p--;
x=h[*p]+1;
}
else if(*p==x)x=h[*p];
else x=h[*p]-1;
p = lower_bound(year.begin(),year.end(),y);
if(p==year.end())
{
p--;
y=h[*p]+1;
}
else if(*p==y)y=h[*p];
else y=h[*p]-1;
int s=logn[x-1-(y+1)+1];
if(x-y<=1)
{
if(!stmax[x][0]||!stmax[y][0])cout<<"maybe"<<endl;
else if(stmax[x][0]<stmax[y][0])cout<<"true"<<endl;
else cout<<"false"<<endl;
continue;
}
if(!stmax[x][0]||!stmax[y][0])
{
if(!stmax[x][0])
{
if(stmax[y][0]&&max(stmax[y+1][s],stmax[x-1-(1<<s)+1][s])>=stmax[y][0])cout<<"false"<<endl;
else cout<<"maybe"<<endl;
}
else
{
if(stmax[x][0]>max(stmax[y+1][s],stmax[x-1-(1<<s)+1][s]))
{
cout<<"maybe"<<endl;
}
else cout<<"false"<<endl;
}
}
else if(stmax[x][0]<=stmax[y][0])
{
if(stmax[x][0]>max(stmax[y+1][s],stmax[x-1-(1<<s)+1][s]))
{
if(!min(stmin[y+1][s],stmin[x-1-(1<<s)+1][s]))cout<<"maybe"<<endl;
else cout<<"true"<<endl;
}
else cout<<"false"<<endl;
}
else cout<<"false"<<endl;
}
}
void init()
{
logn[1]=0;
logn[2]=1;
for(int i=3;i<N;i++)logn[i]=logn[i/2]+1;
}
|
