很裸的一道线段树题，被硬生生刷成了紫题。。可能因为细节问题吧，我也栽了一次WA50分。不过这个隐藏条件真的对本菜鸡来说不易发现啊。
未知的年份连续的就看成一个就好了，把年份都离散化一下。
分四大类(设自X以来的Y年)
- X未知,Y未知.(maybe)
- X未知,Y已知.中间夹住的区间只看有没有超过Y降雨量的就行了(false/meybe)
- X已知,Y已知.看中间有没有超过的有就是false并且注意看X降雨量是不是大于等于Y的降雨量（来自题目第一行），其次再看中间最小值有没有0（我把未知的年份降雨量设为0），来判断false还是true
- X已知,Y未知.有坑！要看X到Y之间有没有超过X降雨量的，有的话Y没法满足条件。
错误笔记:栽在第4点上。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define l i<<1
#define r i<<1|1
#define dbg(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=+,inf=1e9;
int minv[N<<],maxv[N<<],A[N],year[N];
int n,m,q,nen,ryou,ql,qr,x,y,X,Y,minx,maxx;
void build(int i,int L,int R){
if(L==R){minv[i]=maxv[i]=A[L];return;}
int mid=L+R>>;build(l,L,mid),build(r,mid+,R);minv[i]=_min(minv[l],minv[r]);maxv[i]=_max(maxv[l],maxv[r]);
}
int Query_min(int i,int L,int R){
if(ql<=L&&qr>=R)return minv[i];
int mid=L+R>>,ret=inf;
if(ql<=mid)MIN(ret,Query_min(l,L,mid));
if(qr>mid)MIN(ret,Query_min(r,mid+,R));
return ret;
}
int Query_max(int i,int L,int R){
if(ql<=L&&qr>=R)return maxv[i];
int mid=L+R>>,ret=;
if(ql<=mid)MAX(ret,Query_max(l,L,mid));
if(qr>mid)MAX(ret,Query_max(r,mid+,R));
return ret;
} int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
read(n);year[]=-inf-;
for(register int i=;i<=n;++i){
read(nen),read(ryou);
if(nen-==year[m])year[++m]=nen,A[m]=ryou;
else ++m,year[m]=year[m-]+,year[++m]=nen,A[m]=ryou;
}
if(year[m]<inf)++m,year[m]=year[m-]+;
build(,,m);read(q);
while(q--){
read(x),read(y);
X=upper_bound(year+,year+m+,x)-year-;
Y=upper_bound(year+,year+m+,y)-year-;//dbg(X),dbg(Y),dbg(A[X]),dbg(A[Y]);
if(!A[X]){
if(X+==Y||!A[Y])printf("maybe\n");
else{
ql=upper_bound(year+,year+m+,x+)-year-;
qr=upper_bound(year+,year+m+,y-)-year-;
maxx=Query_max(,,m);
if(maxx>=A[Y])printf("false\n");
else printf("maybe\n");
}
}
else{
if(A[Y]>A[X]){printf("false\n");continue;}
if(!A[Y]){
if(X+==Y){printf("maybe\n");continue;}
ql=upper_bound(year+,year+m+,x+)-year-;
qr=upper_bound(year+,year+m+,y-)-year-;//dbg(ql),dbg(qr);
maxx=Query_max(,,m);
if(maxx>=A[X])printf("false\n");
else printf("maybe\n");
}
else if(X+==Y)printf("true\n");
else{
ql=upper_bound(year+,year+m+,x+)-year-;
qr=upper_bound(year+,year+m+,y-)-year-;//dbg(ql),dbg(qr);
maxx=Query_max(,,m);minx=Query_min(,,m);//dbg(minx),dbg(maxx);
if(maxx>=A[Y])printf("false\n");
else if(!minx)printf("maybe\n");
else printf("true\n");
}
}
}
return ;
}