不懂就问
查看原帖
不懂就问
750163
_Kenma_楼主2024/3/6 22:18

为什么h数组开1e5会re……,改成2e5就A了

#include<bits/stdc++.h>
using namespace std;
int n,m,h[100005];
int val[35][200005],pos[200005];
void build(int l,int r,int d,int x){
	if(l==r){
		pos[l]=x;
		return;
	}
	int mid=(l+r)>>1;
	val[d][mid]=h[mid];
	val[d][mid+1]=h[mid+1];
	for(int i=mid-1;i>=l;i--){
		val[d][i]=max(val[d][i+1],h[i]);
	}
	for(int i=mid+2;i<=r;i++){
		val[d][i]=max(val[d][i-1],h[i]);
	}
	build(l,mid,d+1,x<<1);
	build(mid+1,r,d+1,x<<1|1);
}
int logn[400005];
void pre_log(int a){
	for(int i=2;i<=a;i++){
		logn[i]=logn[i>>1]+1;
	} 
}
int query(int l,int r){
	int d=logn[pos[l]]-logn[pos[l]^pos[r]];
	return max(val[d][l],val[d][r]);
}
int l,r;
int len;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(len=2;len<n;len<<=1);
	pre_log(len<<1);
	build(1,len,1,1);
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		cout<<query(l,r)<<'\n';
	}
	return 0;
} 
2024/3/6 22:18
加载中...