Cogs 58. 延綿的山峰(st表)

2019-11-14 09:36:22

字體：大中小

來源：轉載

供稿：網友

延綿的山峰 ★★☆ 輸入文件：climb.in 輸出文件：climb.out 簡單對比時間限制：1 s 內存限制：512 MB 問題描述有一座延綿不斷、跌宕起伏的山，最低處海拔為0，最高處海拔不超過8848米，從這座山的一端走到另一端的過程中，每走1米海拔就升高或降低1米。有Q個登山隊計劃在這座山的不同區段登山，當他們攀到各自區段的最高峰時，就會插上隊旗。請你寫一個程序找出他們插旗的高度。輸入文件第1行，一個整數N(N<=10^6)，表示山兩端的跨度。接下來N+1行，每行一個非負整數Hi，表示該位置的海拔高度，其中H0=Hn=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 /*還是裸題.維護max. 不過第一次RE了.原因是line :for(int i=0;i<=n;i++)然后改成了for(int i=0;i<=n-mi[j-1];i++).因為[n-mi[j-1],n]這一塊對答案是沒有貢獻的.這樣的話就算上n后面的貢獻了.要是求min就尷尬了.*/#include<iostream>#include<cstdio>#include<cmath>#define MAXN 1000001#define D 21using namespace std;int n,m,a[MAXN],f[MAXN][D+5],mi[D+5];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 slove(){ int k=log(n)/log(2)+1; for(int j=1;j<=k;j++) for(int i=0;i<=n-mi[j]+1;i++)//1 R. f[i][j]=max(f[i][j-1],f[i+mi[j-1]][j-1]); return ;}int query(int l,int r){ int k=log(r-l+1)/log(2); return max(f[l][k],f[r-mi[k]+1][k]);}int main(){ freopen("climb.in","r",stdin); freopen("climb.out","w",stdout); int x,y; n=read();mi[0]=1; for(int i=1;i<=D;i++) mi[i]=mi[i-1]<<1; for(int i=0;i<=n;i++) a[i]=read(),f[i][0]=a[i]; slove();m=read(); while(m--) { x=read(),y=read();