st表维护区间最值下标

#include<bits/stdc++.h>
using namespace std;
const int Max=1000005;
//
int n,m,arr[Max],st[Max][25];
//区间 st[i(下标)][j(2^j 区间长度)] 
// st[i][j]: (i, i+2^j -1)区间 最值的下标 
inline int get_ans(int l,int r){
	int tmp=log2(r-l+1);
	return max(st[l][tmp],st[r-(1<<tmp)+1][tmp]);
}
inline int get_id(int l,int r){
	if(l>r) return 0;
	int tmp=log2(r-l+1);
	int x=st[l][tmp];
	int y=st[r-(1<<tmp)+1][tmp];
	if(arr[x]<arr[y])return y;
	else return x; 
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&arr[i]);
		st[i][0]=i;
	} 
	for(int j=1;(1<<j)<=n;++j){
		for(int i=1;i<=n-(1<<j)+1;++i){
			//st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			//下标 
			int x=st[i][j-1];
			int y=st[i+(1<<j-1)][j-1];
			
			if(arr[x]>arr[y]) st[i][j]=x;
			else st[i][j]=y; 
		}
	}
	
	while(m--){
		int l,r; 
		scanf("%d%d",&l,&r);
		int id=get_id(l,r);
	//	cout<<id<<endl;
		int first_number=arr[id]; 
		int second_number=max(arr[get_id(l,id-1)],arr[get_id(id+1,r)]);
		printf("%.2lf\n",first_number*1.0*second_number/2.0);
	}
	return 0;
}