bzoj1067 降雨量

Posted on |

满足$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;
}