30分,改了一中午,jiujiuwo
查看原帖
30分,改了一中午,jiujiuwo
112375
1a2b3楼主2023/3/20 14:13
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct year{
	int id,sum,i;
}y[50005];
int n,m,tree[200505];
void build(int rt,int l,int r)
{
	if(l==r)
	{
		tree[rt]=y[l].i;
		return;
	}
	int mid=(l+r)>>1;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	if(y[tree[rt*2]].sum>y[tree[rt*2+1]].sum)
		tree[rt]=tree[rt*2];
	else tree[rt]=tree[rt*2+1];
}
int query(int rt,int l,int r,int head,int tail)
{
	if(l>tail||r<head)return 0;
	if(l>=head&&r<=tail)
	{
		return tree[rt];
	}
	if(l==r)return tree[rt];
	int mid=(l+r)>>1;
	int fx=query(rt*2,l,mid,head,tail),fy=query(rt*2+1,mid+1,r,head,tail);
	if(y[fx].sum>y[fy].sum)
		return fx;
	else return fy;
return 0;
}
int erfen(int l,int r,int rt)
{
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(y[mid].id>rt)
			r=mid-1;
		else l=mid+1;
	}
	return r;
}
signed main()
{
	freopen("2471.in","r",stdin);
	freopen("2471.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&y[i].id,&y[i].sum);
		y[i].i=i;
	}
	build(1,1,n);
	y[0].sum=-0x3f3f3f3f;
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		int Y,X,iy=0x3f3f3f3f,ix=0x3f3f3f3f;
		scanf("%lld%lld",&Y,&X);
		if(Y>X)
		{
			printf("false\n");
			continue;
		}
		iy=erfen(1,n,Y); 
		ix=erfen(1,n,X);
//		cout<<iy<<" "<<ix<<endl;
		int pd=query(1,1,n,iy+1,ix);
		if(y[iy].id!=Y&&y[ix].id!=X)//无头无尾 
		{
			printf("maybe\n");
			continue;
		}
		if(y[ix].id!=X)//无尾 
		{
			pd=query(1,1,n,iy,ix);
			if(pd==iy)printf("maybe\n");
			else printf("false\n");
			continue;
		}
		if(y[iy].id!=Y)//无头 
		{
			iy++;
			pd=query(1,1,n,iy,ix);
			if(pd==ix)printf("maybe\n");
			else printf("false\n");
			continue;
		}	
		if(y[ix].sum>y[iy].sum)//不满足最初判断条件 
		{
			printf("false\n");
			continue;
		}
		pd=query(1,1,n,iy+1,ix);
		if(abs(ix-iy)!=abs(X-Y))//中间有空 
		{
			if(pd!=ix) //不是最大 
				printf("false\n");
			else printf("maybe\n");//依然最大
			continue;
		}
		if(pd==ix)
		{
			printf("true\n");
			continue;
		}
		else
		{
			printf("false\n");
			continue;
		}
	} 
	return 0;
}

2023/3/20 14:13
加载中...