bzoj1067 降雨量

满足$y$是$x$以来降雨量最大的讨论:

  • true的情况
    • $x,y$降雨量都知道,且中间年份里降雨量最大值小于$x$和$y$,且中间年份没有不确切的数字
  • maybe的情况(此时要满足$x$的降雨量严格大于$y$的降雨量,否则$false$)
    • $x$,$y$都不知道
    • 两者只有一个知道
    • 都知道,且中间年份里降雨量最大值小于$x$和$y$,但中间年份有不确切的数字
    • $y$小于等于最小的已知降雨量的年份
    • $x$大于等于最大的已知降雨量的年份
      其他的均为$false$
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
#include <bits/stdc++.h>
using namespace std;
const int maxn=50000+5;
const int maxm=10000+5;
#define lson (o<<1)
#define rson (o<<1|1)
int a[maxn+maxm*2];
struct interval_tree{
int maxv[(maxn+maxm*2)<<3];
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r) {maxv[o]=a[l];return;}
else{
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
maxv[o]=max(maxv[lson],maxv[rson]);
}
}
int Qmax(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return INT_MIN;
if(ql<=l && r<=qr) return maxv[o];
else{
int mid=(l+r)>>1,ret=INT_MIN;
if(ql<=mid) ret=max(ret,Qmax(lson,l,mid,ql,qr));
if(qr>mid) ret=max(ret,Qmax(rson,mid+1,r,ql,qr));
return ret;
}
}
} Tree;
int n,m;
pair<int ,int > p[maxn],q[maxm];
vector<int > val,yr;
map<int ,int > rfl,rrfl,yrfl;
void ok() {printf("true\n");}
void ko() {printf("false\n");}
void oo() {printf("maybe\n");}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&p[i].first,&p[i].second);
val.push_back(p[i].first);yr.push_back(p[i].first);
}
for(int i=0;i<(int)yr.size();i++) yrfl[yr[i]]=i+1;
scanf("%d",&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&q[i].first,&q[i].second);
val.push_back(q[i].first),val.push_back(q[i].second);
val.push_back(q[i].first+1),val.push_back(q[i].second-1);
}
sort(val.begin(),val.end());
int sz=unique(val.begin(),val.end())-val.begin();
for(int i=0;i<sz;i++) rfl[val[i]]=i+1,rrfl[i+1]=val[i];
for(int i=1;i<=n;i++){
a[rfl[p[i].first]]=p[i].second;
}
Tree.build(1,1,sz);
for(int i=1;i<=m;i++){
if(q[i].first>=q[i].second) ko();
else {
if(q[i].first==q[i].second-1){
if(a[rfl[q[i].first]]==0 || a[rfl[q[i].second]]==0) oo();
else {
if(a[rfl[q[i].first]]>a[rfl[q[i].second]]) ok();
else ko();
}
}else{
int l=rfl[q[i].first+1],r=rfl[q[i].second-1];
assert(l<=r);
int tmp=Tree.Qmax(1,1,sz,l,r);
int x=rfl[q[i].first],y=rfl[q[i].second];
if(!a[x] && !a[y]) oo();
else if(!a[x]) {
if(x==sz) oo();
else if(tmp<a[y]) oo();
else ko();
}else if(!a[y]) {
if(y==1) oo();
else if(tmp<a[x]) oo();
else ko();
}else{
int yl=yrfl[q[i].first],yr=yrfl[q[i].second];
if(a[x]<a[y]) ko();
else if(tmp>=a[x] || tmp>=a[y]) ko();
else {
if(yr-yl+1<q[i].second-q[i].first+1) oo();
else ok();
}
}
}
}
}
return 0;
}