降雨量求调,玄关
查看原帖
降雨量求调,玄关
1364148
yangzimu0131楼主2025/1/15 17:40
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int mx,f;
}tree[400010];
struct data{
	int t,num;
}a[400010];
int b[400010],cnt;
map<int,int> mp;
bool f;
void build(int k,int l,int r)
{
    //cout<<k<<" "<<l<<" "<<r<<endl;
	if(l==r)
	{
		if(a[l].num==0)
			tree[k].mx=-1,tree[k].f=1;
		else
			tree[k].mx=a[l].num;
        //cout<<k<<" "<<l<<" "<<tree[k].mx<<endl;
        return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);
	tree[k].f=tree[k<<1].f|tree[k<<1|1].f;
}
int query(int k,int l,int r,int x,int y)
{
	if(l>r)
		return 0;
	if(x<=l&&r<=y)
	{
		f=tree[k].f;
		return tree[k].mx;
	}
	int ans=-2e9,mid=(l+r)>>1,sum;
	if(x<=mid)
	{
		sum=query(k<<1,l,mid,x,y);
		ans=max(ans,sum);
	}
	if(y>mid)
	{
		sum=query(k<<1|1,mid+1,r,x,y);
		ans=max(ans,sum);
	}
	//cout<<k<<" "<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<ans<<" "<<f<<endl;
	return ans;
}
bool cmp(data x,data y)
{
	return x.t<y.t;
}
signed main()
{
	int n,m,x,y,temp,mx=0,lst=0,k,l;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		if((i==1||x-lst==1)||(lst==-1&&x==1))
		{
			lst=x;
			a[++cnt].t=x;
			a[cnt].num=y;
			continue;
		}
		//cout<<"adasdasdasd";
		//cout<<x<<" "<<lst<<endl;
		a[++cnt].t=lst+1;
		a[cnt].num=0;
		a[++cnt].t=x;
		a[cnt].num=y;
		lst=x;
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		mp[a[i].t]=i;
		b[i]=a[i].t;
		//cout<<i<<" "<<a[i].t<<" "<<a[i].num<<" "<<mp[a[i].t]<<endl;
		
	}
	build(1,1,cnt);
	for(int i=1;i<=cnt;i++)
	{
		mp[a[i].t]=i;
		b[i]=a[i].t;
		//cout<<i<<" "<<a[i].t<<" "<<a[i].num<<" "<<mp[a[i].t]<<endl;
		//cout<<query(1,1,cnt,i,i)<<endl;
	}
    //cout<<query(12,4,4,2,4)<<endl;
    //cout<<a[4].num<<endl;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		f=0;
		cin>>x>>y;
		if(x>=y)
		{
			cout<<"false\n";
			continue;
		}
		k=lower_bound(b+1,b+cnt+1,x+1)-b;
		if(!mp[b[k]-1])
			k--;
		l=mp[y];
		if(l==0)
			l=lower_bound(b+1,b+cnt+1,y)-b;
		//cout<<k<<" "<<l<<endl;
		if(k>=l||l-k-1>=0)
		{
			cout<<"maybe\n";
			continue;
		}
		 
		temp=query(1,1,cnt,k,l-1);
        //cout<<temp<<" "<<a[l].num<<" "<<l<<" "<<f<<endl;
		if(a[k-1].num<a[l].num)
			cout<<"false\n";
		else if(temp>=a[l].num)
			cout<<"false\n";
		else if(f)
			cout<<"maybe\n";
		else
			cout<<"true\n";
	}
	return 0;
}
2025/1/15 17:40
加载中...