复习板子. 远古代码概不负责.
ST表基于二进制划分思想, 用于求静态RMQ, $latex O(N\log N)$预处理, $latex O(1)$查询.
设$latex max[i][j]$表示区间$latex [i,i+2^j-1]$的最大值, 即从$latex i$开始长度为$latex 2^j$区间的最大值, 类似于树上倍增. 这个数组很容易预处理出来, 有DP方程$latex max[i][j]=max( max[i][j-1] , max[i+2^{j-1}][j-1] )$, 即左右两半合并.
求区间$latex [l,r]$的最大值时, 找出一个整数$latex t$使得 $latex 2^t <$ 区间长度 $latex <= 2^{t+1}$. 根据整数$latex t$的性质可知 : 以$latex l$开头的$latex 2^t$个数 和 以$latex r$结尾的$latex 2^t$个数 这两段一定覆盖了区间$latex [l,r]$, 取$latex max$即可.
#include<cstdio>
#define re register
inline int read()
{
int s=0,b=1;
char ch;
do{
ch=getchar();
if(ch=='-') b=-1;
}while(ch<'0' || ch>'9');
while(ch>='0' && ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return b*s;
}
int n,m,max[110000][31];
int k[110000];//k[i]=(int)log_2(i);
int main()
{
n=read();
m=read();
int cnt=1;
k[1]=0;
for(re int i=2;i<=n;i++)
{
if((1<<(cnt+1))==i) cnt++;
k[i]=cnt;
//printf("%d ",k[i]);
}//预处理出log_2(1~n)的值;
for(re int i=1;i<=n;i++) max[i][0]=read(); //显然,元区间[i,i]的最值即原数本身
for(re int j=1;j<31;j++)
for(re int i=1;i+(1<<j)-1<=n;i++) //注意整个区间[i,i+2^j-1]都不能越界
max[i][j]=max[i][j-1]>max[i+(1<<(j-1))][j-1]?max[i][j-1]:max[i+(1<<(j-1))][j-1];//显然,区间 [i,i+2^j-1]的最值为 其左半边[i,i+2^(j-1)-1]最值 与 其右半边[i+2^(j-1),i+2^j-1]最值 中的最大值
int l,r;
for(re int i=1;i<=m;i++)
{
l=read();
r=read();
int t=k[r-l+1]; //找出一个整数t使得 2^t < 区间长度 <= 2^(t+1)
printf("%d\n",max[l][t]>max[r-(1<<t)+1][t]?max[l][t]:max[r-(1<<t)+1][t]);
//[l,r]的max: max( max[l][t] , max[r-(2^t+1)][t])
//根据整数t的性质可知 : 以l开头的2^t个数 和 以r结尾的2^t个数 这两段一定覆盖了区间[l,r], 取max即可
}
return 0;
}
CGaZn的博客
最新评论