- [倍增基础]RMQ
题目ID：7144必做题100分
最新提交：
Time Limit Exceeded
50 分
历史最高：
Time Limit Exceeded
50 分
时间限制: 1000ms
空间限制: 256000kB
题目描述
[题目描述]
给你一个长度为n的数组，有q组询问，每次询问一个区间内所有数字的极差（max-min）。
[输入格式]
第一行，一个正整数n，表示数组长度。
第二行，n个正整数a[i]，表示给定数组。
第三行，一个正整数q，表示询问数。
接下来q行，每行两个正整数l,r，表示询问的区间。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],q,f1[N][20],f2[N][20];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f1[i][0]=a[i];
f2[i][0]=a[i];
}
scanf("%d",&q);
int lgn=int(log(n)/log(2));
for(int j=1;j<=lgn;j++){
int x=(1<<(j-1));
for(int i=1;i<=n;i++){
f1[i][j]=max(f1[i][j-1],f1[i+x][j-1]);
f2[i][j]=min(f2[i][j-1],f2[i+x][j-1]);
}
}
while(q--){
int l,r;
scanf("%d %d",&l,&r);
int g=int(log(r-l+1)/log(2));
printf("%d\n",max(f1[l][g],f1[r-(1<<g)+1][g])-min(f2[l][g],f2[r-(1<<g)+1][g]));
}
}
1~5AC,6~10TLE，真无语
哪位大佬能帮忙看一下？