【cogs58】延绵的山峰【st表】

山峰【st表】"/>

【cogs58】延绵的山峰【st表】

问题描述 有一座延绵不断、跌宕起伏的山，最低处海拔为0，最高处海拔不超过8848米，从这座山的一端走到另一端的过程中，每走1米海拔就升高或降低1米。有Q个登山队计划在这座山的不同区段登山，当他们攀到各自区段的最高峰时，就会插上队旗。请你写一个程序找出他们插旗的高度。 输入文件 第1行，一个整数N(N<=10^6)，表示山两端的跨度。 接下来N+1行，每行一个非负整数Hi，表示该位置的海拔高度，其中H 0=H n=0。 然后是一个正整数Q(Q<=7000)，表示登山队的数量。 接下来Q行，每行两个数Ai, Bi，表示第i个登山队攀爬的区段[Ai,Bi]，其中0<=Ai<=Bi<=N。 输出文件 Q行，每行为一个整数，表示第i个登山队插旗的高度。
样例输入 10 0 1 2 3 2 3 4 3 2 1 0 5 0 10 2 4 3 7 7 9 8 8 样例输出 4 3 4 3 2 题解：st表的模板题。。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,f[1000011][30],a,b,q;
int main()
{freopen("climb.in","r",stdin);freopen("climb.out","w",stdout); scanf("%d",&n);for (int i=1;i<=n+1;i++){scanf("%d",&a);f[i][0]=a;}for (int i=1;i<=20;i++)for (int j=1;j<=n;j++)if (j+(1<<i)-1<=n) f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);else break;scanf("%d",&q);for (int i=1;i<=q;i++){int temp;scanf("%d%d",&a,&b);a++;b++;temp=(int)(log(b-a+1.0)/log(2.0));printf("%d\n",max(f[a][temp],f[b-(1<<temp)+1][temp]));}
}