//
Q: 长度为 n 的数组 q 次询问 区间最大值1<=n,q<=5e5;
1<=l<=r<=n;
-1e9<=k,ai<=1e9;样例输入
5 5
1 2 3 4 5
1 1
1 2
1 3
3 4
2 5样例输出
1
2
3
4
5
//
A:
#include<bits/stdc++.h>
using namespace std;// 1<=n,q<=5e5
const int MAXN=1e6+7;// printf("%lf\n",log2(1e6)); == 19.931569
int a[MAXN],dp_max[MAXN][30];
int n,q;// int group=(int)log2(n);
// int group=(int) ( log( (double)n ) / log( (double)2 ) );// i: 以 i 为起始点的数组区间 j: 2^j 数组区间长度// 1+2^k<=n+1 == 2^k<=n 消去干扰源void st_init()
{int i,j,group=(int)log2(n);memset( dp_max,0,sizeof( dp_max ) ); //for( i=1;i<=n;i++ ) dp_max[i][0]=a[i];for( j=1;j<=group;j++ ){for( i=1; i+(1<<j)<=n+1 ;i++ ){dp_max[i][j]=max( dp_max[i][j-1],dp_max[i+( 1<<(j-1) )][j-1] );}}
}// int len=(int)log2( y-x+1 );
// int len=(int) ( log( (double)(y-x+1) ) / log( (double)2 ) );// y-(1<<len)+1 : +1 复位int st_ask( int x,int y )
{int len=(int)log2( y-x+1 );return max( dp_max[x][len],dp_max[ y-(1<<len)+1 ][len] );
}int main()
{int i,x,y;while( ~scanf("%d%d",&n,&q) ){for( i=1;i<=n;i++ ) scanf("%d",&a[i]);st_init();while( q-- ){scanf("%d%d",&x,&y);printf("%d\n",st_ask( x,y ));}}return 0;
}
//
find:
01 memset()初始化数组 (多组数据)
02 能不能从下标为0开始呢？
03 得学哈希