ST 0分 线段树 93分差十多毫秒 求条

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
const int LOG=17;

int st[N][LOG]={},lg2[N]={},arr[N]={};

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void make_log(int n){
	lg2[1]=0;
	for(int i=2;i<=n;i++){
		lg2[i]=lg2[i/2]+1;
	}
	return ;
}

void build_st(int n){
	for(int i=1;i<=n;i++)
		st[i][0]=arr[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	return ;
}

void qu(int l,int r){
	int k=lg2[r-l+1];
	printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));
	return ;
}
int main(){
	int n;
	n=read();
	for(int i=1;i<=n;i++)
		arr[i]=read();
	make_log(n);
	build_st(n);
	int m;
	m=read();
	while(m--){
		int l,r;
		l=read();
		r=read();
		qu(l,r);
	} 
	return 0;
}

#include<bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int N=1e5+10;
int n,m;
int x,y;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int a[N];
struct tree{
	int l,r,sum,tag;
}t[4*N]; 
inline void build(int l,int r,int x){
	t[x].r=r,t[x].l=l;
	if(r==l){
		t[x].sum=a[l];
		return ;
	} 
	int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	t[x].sum=max(t[ls].sum,t[rs].sum);
}
inline int get_ans(int l,int r,int x){
	if(t[x].l>=l&&t[x].r<=r){
		return t[x].sum;     
	}
	int ans=INT_MIN;
	int mid=(t[x].r+t[x].l)>>1;
	if(l<=mid) ans=max(ans,get_ans(l,r,ls));
	if(r>mid) ans=max(ans,get_ans(l,r,rs));
	return ans;
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,n,1);
	for(int i=1;i<=m;i++){
		x=read();
		y=read();
		printf("%d\n",get_ans(x,y,1));
	}
}