线段树水题。
注意离散，若是两年份中间还有别的未知年份则多加一个点。
然后就是判断很烦，注意读清楚题，条件判断完。
//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
typedef long long LL;
const int maxn=200005;
using namespace std;
int n,m,x,y,sg[maxn<<2],ok[maxn<<2],know[maxn],tp[50005][2],ask[10005][2],yes;
int ls[maxn],yy[maxn],sz,tpsz,ll,rr;
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
void add(int x,int l,int r,int pos,int v) {
if(l==r) {sg[x]=v; ok[x]=1; return;}
if(pos<=mid) add(lc,l,mid,pos,v);
else add(rc,mid+1,r,pos,v);
sg[x]=max(sg[lc],sg[rc]);
if(ok[lc]&&ok[rc]) ok[x]=1;
}
int qry(int x,int l,int r,int ql,int qr) {
if(l>=ql&&r<=qr) {if(!ok[x]) yes=0; return sg[x]; }
if(qr<=mid) return qry(lc,l,mid,ql,qr);
if(ql>mid) return qry(rc,mid+1,r,ql,qr);
return max(qry(lc,l,mid,ql,qr),qry(rc,mid+1,r,ql,qr));
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
memset(sg,128,sizeof(sg));
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&x,&y);
tp[i][0]=x; tp[i][1]=y;
ls[++sz]=x;
}
scanf("%d",&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&y,&x);
ask[i][0]=x; ask[i][1]=y;
ls[++sz]=x; ls[++sz]=y;
}
sort(ls+1,ls+sz+1);
tpsz=unique(ls+1,ls+sz+1)-(ls+1); sz=0;
for(int i=1;i<=tpsz;i++) {
yy[++sz]=ls[i];
if(i+1<=tpsz&&ls[i+1]!=ls[i]+1) yy[++sz]=ls[i]+1;
}
for(int i=1;i<=n;i++) {
x=tp[i][0],y=tp[i][1];
ll=lower_bound(yy+1,yy+sz+1,x)-yy;
add(1,1,sz,ll,y); know[ll]=y;
}
for(int i=1;i<=m;i++) {
x=ask[i][0],y=ask[i][1];
ll=lower_bound(yy+1,yy+sz+1,y)-yy;
rr=lower_bound(yy+1,yy+sz+1,x)-yy;
if(ll==rr) printf("true
");
else if(rr==ll+1) {
if(know[ll]&&know[rr]&&know[rr]<=know[ll]) printf("true
");
else if(!know[ll]||!know[rr]) printf("maybe
");
else printf("false
");
}
else {
yes=1;
int ma=qry(1,1,sz,ll+1,rr-1);
if((know[rr]&&know[rr]<=ma)||(know[ll]&&(know[ll]<know[rr]||know[ll]<=ma))) printf("false
");
else if(!yes||!know[ll]||!know[rr]) printf("maybe
");
else printf("true
");
}
}
return 0;
}