加了一些注解
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const int N=5e4+10;
int n,m;
inline int read() //快读
{
int x=0,f=1;
char c;c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c-'0');
c=getchar();
}
return x*f;
}
struct node{
int yi,li,ri;//yi 降雨量 li--区间左端点年份 ri--区间右端点年份
}a[N*4];
void build(int k,int l,int r)//建树
{
if(l==r)
{
a[k].li=read();
a[k].yi=read();
a[k].ri=a[k].li;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
a[k].yi=max(a[k<<1].yi,a[k<<1|1].yi);//存区间最大值
a[k].li=a[k<<1].li;
a[k].ri=a[k<<1|1].ri;
}
int ask(int k,int l,int r,int x) //单点询问,若未知则输出0
{
if(x<a[k].li||x>a[k].ri)return 0;
if(x==a[k].li&&a[k].li==a[k].ri)return a[k].yi;
int mid=l+r>>1;
return max(ask(k<<1,l,mid,x),ask(k<<1|1,mid+1,r,x));
}
int query(int k,int l,int r,int x,int y)//询问【x,y】区间最大值
{
if(y<a[k].li||x>a[k].ri)return 0;
if(x<=a[k].li&&a[k].ri<=y)return a[k].yi;
int mid=l+r>>1;
return max(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
}
bool lll(int k,int l,int r,int x,int y)//判断【x,y】区间是否有年份未知
{
if(y<a[k].li||x>a[k].ri)return 0;
if(x<=a[k].li&&a[k].ri<=y)
{
if(a[k].ri-a[k].li!=r-l)return 1;
return 0;
}
int mid=l+r>>1;
return max(lll(k<<1,l,mid,x,y),lll(k<<1|1,mid+1,r,x,y));
}
int main()
{
int i,j;
n=read();
build(1,1,n);
m=read();
// for(i=1;i<=11;i++)
// cout<<a[i].li<<" "<<a[i].ri<<" "<<a[i].yi<<endl;
while(m--)
{
int x,y;
y=read();x=read();
if(y>=x)
{
printf("false\n");
continue;
}
int x1=ask(1,1,n,x),yy=ask(1,1,n,y),q=query(1,1,n,y+1,x-1);
// cout<<x1<<" "<<yy<<" "<<q<<" ";
if(x1>0&&q>=x1)//左端点年份确定,且中间年份最大降雨量大于等于右端点降雨量
{
printf("false\n");
continue;
}
if(yy>0&&q>=yy)//当左端点年份确定,且中间年份最大降雨量大于等于左端点降雨量
{
printf("false\n");
continue;
}
if(x1>0&&yy>0&&yy<=x1)//左右端点年份都确定,左端点降雨量小于等于右端点降雨量
{
printf("false\n");
continue;
}
if(x1==0||yy==0)//左端点或右端点年份不确定
{
printf("maybe\n");
continue;
}
if(lll(1,1,n,y,x)>0)//区间内有年份未知
{
printf("maybe\n");
continue;
}
printf("true\n");
}
return 0;
}