10pts,求助!
查看原帖
10pts,求助!
907430
corner_xiejunqi楼主2024/10/20 12:56

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,m;
const int N=5e5+10;
struct node{
	int year,num;
}e[N];
map<int,int> mp,mp1;
int st[40][N],lg[N];
void init_st(){
	for(int i=1;i<=n;i++){
		st[0][i]=e[i].num;
	}
	for(int k=0;(1<<(k+1))<=n;k++){
		for(int i=1;i<=n-(1<<(k+1))+1;i++){
			st[k+1][i]=max(st[k][i],st[k][i+(1<<k)]);
		}
	}
}
void init_lg(){
	for(int k=0,i=1;i<=n;i++){
		if(i==(1<<(k+1))) k++;
		lg[i]=k;
	}
}
int find(int l,int r){
	int k=lg[r-l+1];
	return max(st[k][l],st[k][r-(1<<k)+1]);
}
signed main(){
	// step 1、读题、声明变量
	// step 2、输入
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>e[i].year>>e[i].num;
		mp[e[i].year]=e[i].num;
		mp1[e[i].year]=i;
	}
	cin>>m;
	int start_year,end_year;
	init_st();
	init_lg();
	while(m--){
		cin>>start_year>>end_year;
		int maxn=find(mp1[start_year]+1,mp1[end_year]);
		//cout<<maxn<<'\n';
		//cout<<maxn<<' '<<mp[end_year]<<endl;
		if(mp1[end_year]!=0&&mp1[start_year]!=0){
			int yearc=end_year-start_year+1;
			int xiabiao=mp1[end_year]-mp1[start_year]+1;
			if(yearc==xiabiao){
				int maxz=find(mp1[start_year]+1,mp1[end_year]-1);
				if(mp[end_year]<=mp[start_year] && mp[end_year]>maxz&&mp1[start_year]+1<=mp1[end_year]-1){
					cout<<"true"<<'\n';
					continue;
				}
			}
		}
		if(mp[end_year]>mp[start_year] &&mp1[end_year]!=0&&mp1[start_year]!=0){
			cout<<"false"<<'\n';
			continue;
		}
		int maxz=find(mp1[start_year]+1,mp1[end_year]-1);
		if(mp1[end_year]!=0 && mp[end_year]<=maxz){
			cout<<"false"<<'\n';
			continue;
		}
		if(mp1[start_year]!=0&&mp[start_year]<=maxz&&mp1[start_year]+1<=mp1[end_year]-1){
			cout<<"false"<<'\n';
			continue;
		}
		cout<<"maybe"<<'\n';
	}
	// step 3、处理

	// step 4、输出
	
	return 0;
}

/**
真:
1.终点和起点有
2.年份连续
3.终点必须小于等于起点,又大于中间所有的
假:
1.两端点存在,右端点比左端点大
2.右端点存在,右端点比中间的不大 
3.左端点存在,左端点比中间的不大
其他maybe 
*/


2024/10/20 12:56
加载中...