1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
#include <stdlib.h> #include <string.h> int f1[16][50005],dat[50005],f2[16][50005],N,Q; int (int a,int b){return (a>b)?a:b;} int min(int a,int b){return (a<b)?a:b;} void sttable(int n){ int i,j,p; memcpy(f1[0],dat,sizeof(dat)); memcpy(f2[0],dat,sizeof(dat)); for(i=1;(1<<i)<=n;i++) for(j=0,p=(1<<(i-1));j<n-p;j++) f1[i][j]=max(f1[i-1][j],f1[i-1][j+p]), f2[i][j]=min(f2[i-1][j],f2[i-1][j+p]); }int rmq(int l,int r){ int k=0;while((1<<(k+1))<(r-l+1))k++; return max(f1[k][l],f1[k][r-(1<<k)+1])-min(f2[k][l],f2[k][r-(1<<k)+1]); }int main(){ scanf("%d%d",&N,&Q); int i,l,r; for(i=0;i<N;i++) scanf("%d",&dat[i]); sttable(N); for(i=0;i<Q;i++) scanf("%d%d",&l,&r), printf("%dn",rmq(l-1,r-1)); return 0; }
|
近期评论