P2471 50pts求助,悬关
查看原帖
P2471 50pts求助,悬关
977901
int4399楼主2024/7/30 13:08
#include<bits/stdc++.h>
using namespace std;
int n,m,a[50005],b[50005];
struct tree{
	int l,r,maxx;
}tr[200005];
void pushup(int u){
	tr[u].maxx=max(tr[u<<1].maxx,tr[u<<1|1].maxx);
}
void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r;
	if(l==r){
		tr[u].maxx=b[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
	pushup(u);
}
int check(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].maxx;
	int res=0,mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) res=max(res,check(u<<1,l,r));
	if(r>mid) res=max(res,check(u<<1|1,l,r));
	return res;
}
string solve(bool lflag,bool rflag,int fl,int fr,int l,int r){//lflag和rflag表示该点是否不确定
    if(lflag&&rflag) return "maybe";
	if(r-l==1){
		if(lflag||rflag) return "maybe";
        if(b[fr]>b[fl]) return "false";
        return "true";
	} 
	int maxx=check(1,fl+1,fr-1);
	if(!rflag&&maxx>=b[fr]) return "false";          
	if(!lflag&&maxx>=b[fl]) return "false";
	if(!rflag&&!lflag&&b[fr]>b[fl]) return "false";
	if(lflag||rflag||fr-fl!=r-l) return "maybe";
	return "true";
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	cin>>m;
	build(1,1,n);
	int y,x;
	for(int i=1;i<=m;i++){
		bool flag1=0,flag2=0;
		cin>>y>>x;//x是右,y是左
		int fx=lower_bound(a+1,a+1+n,x)-a,fy=lower_bound(a+1,a+1+n,y)-a;
		if(a[fx]!=x) flag1=true;
		if(a[fy]!=y) flag2=true;
		cout<<solve(flag2,flag1,fy,fx,y,x)<<endl;
	}
	return 0;
}
2024/7/30 13:08
加载中...