st表0分,求调
查看原帖
st表0分,求调
754444
tamamocross楼主2023/9/27 17:17

rt

#include<iostream>
#include<map>
using namespace std;
const int Max=50001,INF=0x3f3f3f3f;
map	<int,int> mp;
int a[Max],b[Max],Log[Max],st[Max][30];
int query(int x,int y){
	int len=Log[y-x+1];
	return max(st[x][len],st[y-(1<<len)+1][len]);	
}
int main(){
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>st[i][0];
		mp[a[i]]=i;
	}
	Log[1]=0,Log[2]=1;
	for(int i=3;i<Max;i++){
		Log[i]=Log[i/2]+1;
	}
	for(int i=1;i<=Log[n];i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		//	cout<<j<<" "<<j+(1<<i)-1<<" "<<st[j][i]<<endl;	
		}	
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(mp.find(x)==mp.end()||mp.find(y)==mp.end()){
			cout<<"maybe"<<endl;
		}else{
			int p1=mp[x],p2=mp[y];
			int q=query(p1+1,p2);
			if(st[p1][0]>=st[p2][0]&&q==st[p2][0]){
				if(p2-p1==a[p2]-a[p1]){
					cout<<"true"<<endl;
				}else{
					cout<<"maybe"<<endl;
				}	
			}else{
				cout<<"false"<<endl;
			}	
		}
	}
} 
2023/9/27 17:17
加载中...